Fişierul intrare/ieşire:2sec.in, 2sec.outSursă.campion 2006
AutorDan-Ionut FecheteAdăugată deastronomyAirinei Adrian astronomy
Timp execuţie pe test0.175 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultateN/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.in2sec.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content