- Time limit: 2.00 s
- Memory limit: 512 MB
Uolevi on ohjelmoinut algoritmin, joka laskee taulukosta suurimman epätyhjän välin summan. Kuitenkin aina kun Uolevi on juuri saanut suoritettua algoritminsa, Kaaleppi käy vaihtamassa taulukosta yhden arvon, ja suoritus on taas aloitettava täysin alusta.
Tehtäväsi on laskea suurin yhtenäisen välin summa taulukossa aina jokaisen muutoksen jälkeen.
Syöte
Ensimmäisellä rivillä on luvut ja . on taulukon pituus ja on muutoksien lukumäärä.
Seuraavalla rivillä on lukua , taulukon alkuarvot.
Seuraavat riviä sisältävät muutokset. Jokainen muutos on kaksi välein eroteltua lukua ja , mikä tarkoittaa, että kohtaan asetetaan arvo .
Tuloste
Tulosta jokaista muutosta kohti yksi rivi, jolla lukee taulukon suurin epätyhjän välin summa muutoksen jälkeen.
Rajat
Esimerkki
Syöte:
5 3 1 2 -1 2 2 3 -5 1 4 3 -1
Tuloste:
4 6 9
Selitys:
Aluksi taulukko on [1 2 -1 2 2]
Muutos 3: -5, uusi taulukko [1 2 -5 2 2]
Suurin summa on välillä :
Muutos 1: 4, uusi taulukko [4 2 -5 2 2]
Suurin summa on välillä :
Muutos 3: -1, uusi taulukko [4 2 -1 2 2]
Suurin summa on välillä :