| Fişierul intrare/ieşire: | 2sec.in, 2sec.out | Sursă | .campion 2006 |
| Autor | Dan-Ionut Fechete | Adăugată de |  Airinei Adrian •astronomy |
| Timp execuţie pe test | 0.175 sec | Limită de memorie | 36864 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
2sec
Singura avere a taranului Ion este formata din N meri aliniati perfect intr-un sir, meri pe care Ion i-a numerotat de la 1 la N. De la o vreme incoace Ion simte ca il lasa puterile si isi da seama ca va trebui sa dea o parte din meri spre folosinta celor 2 fii ai lui. Dar Ion nu poate uita cum fiul cel mic i-a facut zilele amare de cand a crescut si hotaraste urmatoarele:
- fiecare dintre cei doi fii va primi o secventa de meri situati pe pozitii consecutive in sirul merilor
- numarul de meri din secventa primului fiu poate sa difere de numarul de meri din secventa celui de al doilea fiu, dar fiecare fiu va primi cel putin un mar
- fiul cel mic va primi meri cu numere de ordine strict mai mici decat fiul cel mare
- diferenta dintre profitul adus de merii fiului cel mare si profitul adus de merii fiului cel mic trebuie sa fie maxima
Profitul adus de un mar este calculat de Ion dupa formule complicate, perfectionate in decursul anilor.
Cerinta
Scrieti un program care gaseste aceasta diferenta pentru Ion.
Date de intrare
Pe prima linie a fisierului de intrare 2sec.in se afla un numarul natural N reprezentand numarul de meri. Pe urmatoarea linie se gasesc N numere intregi separate prin cate un spatiu, al i-lea numar reprezentand profitul adus de al i-lea mar.
Date de iesire
Fisierul de iesire 2sec.out va contine o singura linie pe care se va afla diferenta maxima care poate fi obtinuta respectand cerintele lui Ion.
Restrictii
- 2 ≤ N ≤ 1 001 000
- -127 ≤ profitul adus de un mar ≤ 127
Exemplu
| 2sec.in | 2sec.out |
|---|---|
| 10 8 -5 1 -3 7 -3 2 8 -3 1 | 21 |
Explicatie
Fiul cel mic primeste merii cu numerele de ordine 2, 3, 4 iar fiul cel mare merii cu numerele de ordine 5, 6, 7, 8.
