Fişierul intrare/ieşire:habarnam.in, habarnam.outSursăad-hoc
AutorCatalin FrancuAdăugată deCatalin.FrancuCatalin Francu Catalin.Francu
Timp execuţie pe test0.5 secLimită de memorie8192 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

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.inhabarnam.outExplicaţ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 sa te autentifici pentru a trimite solutii. Click aici