Fișierul intrare/ieșire habarnam.in, habarnam.out Sursă ad-hoc
Autor Cătălin Frâncu Adăugată de avatar Catalin.Francu Cătălin Frâncu Catalin.Francu
Timp de execuție pe test 0.5 sec Limită de memorie 8192 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

Habarnam (clasele 11-12)

Îl porecliseră Habarnam pentru că nu știa nimic. Acest Habarnam purta o pălărie albastră-albastră, pantaloni galben-canar și o bluziță portocalie cu cravată verde. Îi plăceau lui culorile tari. Astfel, gătit ca un papagal, Habarnam hoinărea zile-n șir prin oraș și născocea fel de fel de aiureli pe care le povestea tuturor. În afară de asta le jignea cu orice prilej pe prichinduțe. De aceea, cum îi zăreau de departe bluzița portocalie, prichinduțele făceau calea-ntoarsă și se ascundeau în casele lor. — Nikolai Nosov, Aventurile lui Habarnam

Într-o zi, prichindelul Știetot veni la Habarnam să-i arate ultima lui invenție:

- Ia uite, Habarnam! Am inventat un algoritm liniar care, primind un vector cu N elemente întregi, găsește subsecvența contiguă de sumă maximă!

Și îi explică lui Habarnam ideea algoritmului. Habarnam clipi a neîncredere și zise:

- Dar dacă al cincilea element are valoarea -20 în loc?
- ?!... Habarnam, nu înțelegi, algoritmul merge pe orice vector. Dar ca să te lămurești, uite cum merge și pe acest exemplu.
- Dar dacă acum al treilea element are valoarea 47?
- Tu ești bătut în cap? Dacă îmi dai M modificări, pot rula același algoritm după fiecare modificare.
- Aha, zise Habarnam. Deci tu propui un algoritm de complexitate O(M×N)? Și lumea-mi zice mie Habarnam?

Este Habarnam un geniu neînțeles? Oare chiar există un algoritm mai bun pentru a afla subsecvența de sumă maximă într-un vector care se modifică?

Date de intrare

Fișierul de intrare habarnam.in conține pe prima linie numerele N M, despărțite printr-un spațiu, reprezentând dimensiunea vectorului și numărul de modificări. Pe următoarea linie se găsesc N numere întregi, reprezentând elementele vectorului. Pe ultimele M linii se află câte două numere i x cu semnificația că al i-lea element din vector capătă valoarea x.

Date de ieșire

În fișierul de ieșire habarnam.out se vor tipări M + 1 numere, câte unul pe linie, reprezentând suma maximă a unei subsecvențe contigue din vectorul inițial și după fiecare modificare.

Restricții

  • 1 ≤ N ≤ 50.000
  • 1 ≤ M ≤ 50.000
  • Elementele vectorului sunt cuprinse între -1.000.000.000 și 1.000.000.000, înainte și după fiecare modificare.
  • Subsecvența poate fi vidă (de sumă 0) dacă toate numerele sunt negative.

Exemplu

habarnam.in habarnam.out Explicație
6 2
3 -1 -3 4 -2 5
3 -1
6 1
7
8
5
Inițial, subsecvența maximă este (4, -2, 5) de sumă 7.
După prima modificare, vectorul devine (3, -1, -1, 4, -2, 5). Subsecvența maximă este tot vectorul, de sumă 8.
După a doua modificare, vectorul devine (3, -1, -1, 4, -2, 1). Subsecvența maximă este (3, -1, -1, 4), de sumă 5.

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 3 categorii