Fişierul intrare/ieşire:buline.in, buline.outSursăpreONI 2007, Runda 3
AutorMircea Bogdan PasoiAdăugată defilipbFilip Cristian Buruiana filipb
Timp execuţie pe test0.1 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Buline

Zaharel se plictisea la cursurile de la facultate si a inceput sa deseneze buline: a luat N bilete si pe fiecare a desenat un numar de buline, doar albe sau doar negre. A asezat cele N bilete in cerc si si-a pus urmatoarea intrebare: daca considera ca pe fiecare biletel este scris un numar intreg (x buline albe va reprezenta numarul x , iar x buline negre numarul -x) care este suma maxima a unei secvente de biletele aflate pe pozitii consecutive?

Date de intrare

Fisierul de intrare buline.in va contine pe prima linie numarul natural N. Urmatoarele N linii vor contine cate doua numerele naturale , reprezetand numarul de buline de pe biletele si culoarea lor (0 pentru negru si 1 pentru alb), in ordinea in care acestea au fost asezate.

Date de iesire

Fisierul de iesire buline.out va contine trei numerele naturale: S P L cu semnificatia ca secventa de biletele de suma maxima are suma S, incepe pe pozitia P si are lungime L. Daca exista mai multe solutii se va afisa cea cu pozitia P minima, iar daca exista mai multe solutii cu pozitia P minima se va afisa cea cu lungimea L minima.

Restrictii si observatii

  • 1 ≤ N ≤ 200.000
  • Numarul de buline de pe un biletel este cuprins in intervalul [0, 10.000]
  • Biletele sunt numerotate cu numere de la 1 la N
  • Avand in vedere ca biletele sunt asezate in cerc, dupa biletelul N urmeaza biletelul 1
  • Secventa aleasa trebuie sa fie formata din cel putin un biletel
  • Pentru un test se va acorda 50% din punctaj pentru o solutie corecta, dar pentru care valorile P sau L nu sunt minime

Exemplu

buline.inbuline.out
5
1 0
2 1
4 0
3 1
5 1
9 4 4

Explicatie

Cele 5 biletele, pe fiecare fiind trecut numarul sau si bulinele:

Biletele cu contur rosu sunt cele care formeaza secventa de suma maxima.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content