Mineria P61019

Statement

thehtml

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?

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 · (−2) + 2 · (−1) + 3 · 4 + 2 · 8 + 1 · 0 + 0 · (−3) + 0 · 9 + 1 · 2 + 1 · 3 = 29.

unit=0.25cm

(20,12) -(1,1)(1,11) -(3,1)(3,11) -(5,1)(5,11) -(7,1)(7,11) -(9,1)(9,11) -(11,1)(11,11) -(13,1)(13,11) -(15,1)(15,11) -(17,1)(17,11) -(19,1)(19,11) -(1,1)(19,1) -(1,3)(19,3) -(1,5)(19,5) -(1,7)(19,7) -(1,9)(19,9) -(1,11)(19,11)

fillstyle=hlines hatchcolor=green (1,11)(3,9) (3,11)(5,7) (5,11)(7,5) (7,11)(9,7) (9,11)(11,9) (15,11)(17,9) (17,11)(19,9)

hatchcolor=orange (1,1)(3,3) (3,1)(5,3) (5,1)(7,3) (7,1)(9,7) (9,1)(11,3) (11,1)(13,3) (13,1)(15,11) (15,1)(17,3) (17,1)(19,3)

(2,0.3)-2 (4,0.3)-1 (6,0.3)4 (8,0.3)8 (10,0.3)0 (12,0.3)-3 (14,0.3)9 (16,0.3)2 (18,0.3)3 (2,11.7)1 (4,11.7)2 (6,11.7)3 (8,11.7)4 (10,11.7)5 (12,11.7)6 (14,11.7)7 (16,11.7)8 (18,11.7)9 (0.3,10)0 (0.3,8)1 (0.3,6)2 (0.3,4)3 (0.3,2)4

Entrada

L’entrada consisteix en diversos casos només amb nombres enters, cadascun amb n, seguida de b₁, b₂, …, b_n, seguides de p₁, p₂, …, p_n. Podeu suposar 1 ≤ n ≤ 1000, que les b_i estan entre −10⁹ i 10⁹, i que les p_i estan entre 0 i 10⁹.

Sortida

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

Puntuació

Cas A: ‍ Casos on cap b_i és negativa. ‍40% Punts ‍

Cas B: ‍ Resta de casos. ‍60% Punts ‍

Observació

Us recomanem resoldre aquest problema en C++.

Public test cases

Input

9
-2 -1 4 8 0 -3 9 2 3
4 4 4 2 4 4 0 4 4
9
-2 -1 4 8 0 -3 9 2 3
4 4 4 4 4 4 4 4 4
1
-1000000000
1000000000
4
1000000000 1000000000 1000000000 9999999
5 5 5 5

Output

Information

Author: Salvador Roura
Language: Catalan
Official solutions: C++
User solutions: C++