Mineria P61019


Statement
 

pdf   zip

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 bi que suposaria excavar cada metre vertical. (Nombres negatius indiquen pèrdues.) També, per a cada metre i, s’ha trobat a quina profunditat pi 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 b1, b2, …, bn, seguides de p1, p2, …, pn. Podeu suposar 1 ≤ n ≤ 1000, que les bi estan entre −109 i 109, i que les pi estan entre 0 i 109.

Sortida

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

Puntuació

  • Cas A:  ‍ Casos on cap bi é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

    29
    68
    0
    5009999999
    
  • Information
    Author
    Salvador Roura
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++