Fişierul intrare/ieşire:oracol.in, oracol.outSursăONI 2019, clasele 11-12, ziua 1
AutorCostin OncescuAdăugată deAlexPop28Pop Alex-Nicolae AlexPop28
Timp execuţie pe test0.5 secLimită de memorie131072 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Oracol

Gustavo, după ce a realizat că posedă abilitatea de a vedea în viitor, a decis că a venit momentul să treacă la următorul nivel şi să-şi valorifice capacităţile extrasenzoriale. Pentru a câştiga prestigiu şi a deveni mai cunoscut în rândurile magicienilor profesionişti, acesta a ales să debuteze la Olimpiada
Naţională de Informatică prin prezicerea datelor de intrare pentru anumite probleme propuse în concurs.
Primul client al lui Gustavo, Alfredo, ar dori să afle într-un mod inedit conţinutul unui fişier de intrare aferent unei probleme de concurs, în care sunt scrise elementele unui şir p de N numere întregi. Pentru a face lucrurile mai interesante, Gustavo îi percepe o taxă de C(i,j) bănuţi pentru a-i divulga suma numerelor din şirul p cu indici în intervalul [i,j], anume pi + pi+1 + ... + pj.

Cerinţă

Dându-se valoarea lui N şi toate valorile C(i,j) cu 1 ≤ i ≤ j ≤ N, determinaţi costul total minim pe care trebuie să-l plătească Alfredo pentru a afla toate elementele şirului p.

Date de intrare

În fişierul oracol.in se află pe prima linie numărul natural N. Pe următoarele N linii se află taxele percepute de Gustavo astfel: pe linia i+1 se vor afla N-i+1 numere naturale separate prin câte un spaţiu, reprezentând în ordine costurile C(i,i), C(i,i+1), ... , C(i,N).

Date de ieşire

În fişierul oracol.out trebuie să se găsească un singur număr care reprezintă costul total minim pe care trebuie să-l plătească Alfredo pentru a afla şirul p.

Restricţii

  • 1 ≤ N ≤ 1000
  • pentru orice 1 ≤ i ≤ j ≤ N se garantează 0 ≤ C(i,j) ≤ 1.000.000.
  • pentru teste în valoare de 48 puncte 1 ≤ N ≤ 250.

Exemplu

oracol.inoracol.out
3
4 5 1
6 3
2
6

Explicaţie

Costul total minim este 6 şi se obţine astfel:
Cu un cost de valoare C(1,3)=1 putem afla suma p1 + p2 + p3.
Cu un cost de valoare C(3,3)=2 putem afla valoarea lui p3.
Cu un cost de valoare C(2,3)=3 putem afla suma p2 + p3.
Din acestea putem afla exact toate elementele şirului p.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?