| Fişierul intrare/ieşire: | buline.in, buline.out | Sursă | preONI 2007, Runda 3 |
| Autor | Mircea Bogdan Pasoi | Adăugată de |  Filip Cristian Buruiana •filipb |
| Timp execuţie pe test | 0.1 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate |   3/5 |
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.in | buline.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.
