Mineria P61019

Sota una carretera recta abandonada d’$n$ metres de longitud s’ha descobert un mineral valuós. Per a cada metre $i$ (entre 1 i $n$) de la carretera, s’ha pogut determinar el benefici $b_i$ que suposaria excavar cada metre vertical. (Nombres negatius indiquen pèrdues.) També, per a cada metre $i$, s’ha trobat a quina profunditat $p_i$ hi ha un material tan dur que no es pot seguir excavant. Addicionalment, per seguretat, a cada posició $i$ es permet excavar $j$ metres només si a les posicions $i-1$ i $i+1$ s’han excavat almenys $j-1$ metres. (A les posicions 0 i $n+1$ no es pot excavar.) Podeu calcular el màxim benefici que es pot aconseguir?

0.65 A la dreta teniu el primer exemple d’entrada. A sota de cada columna en podeu veure el benefici per metre excavat. El color carbassa marca el material massa dur. El color verd mostra els metres excavats a la solució òptima. El benefici és $1 \cdot (-2) + 2 \cdot (-1) + 3 \cdot 4 + 2 \cdot 8 + 1 \cdot 0 + 0 \cdot (-3) + 0 \cdot 9 + 1 \cdot 2 + 1 \cdot 3 = 29$.

0.37

Entrada

L’entrada consisteix en diversos casos només amb nombres enters, cadascun amb $n$, seguida de $b_1$, $b_2$, …, $b_n$, seguides de $p_1$, $p_2$, …, $p_n$. Podeu suposar $1 \le n \le 1000$, que les $b_i$ estan entre $-10^9$ i $10^9$, i que les $p_i$ estan entre 0 i $10^9$.

Sortida

Per a cada cas, escriviu el màxim benefici possible.

Puntuació

• Cas A:   Casos on cap $b_i$ és negativa.

• Cas B:   Resta de casos.

Observació

Us recomanem resoldre aquest problema en C++.