CSES - Alitaulukko
  • Time limit: 1.00 s
  • Memory limit: 128 MB

Annettuna on taulukko, jossa on nn kokonaislukua. Lisäksi annettuna on väli [a,b][a,b].

Tehtäväsi on etsiä taulukosta alitaulukko, jonka pituus on vähintään aa, korkeintaan bb ja sen lukujen summan tulee olla mahdollisimman suuri.

Syöte

Syötteen ensimmäisellä rivillä on kolme kokonaislukua nn, aa ja bb.

Seuraavalla rivillä on nn kokonaislukua x1,x2,,xnx_1,x_2,\ldots,x_n: taulukon sisältö.

Tuloste

Tulosta suurin mahdollinen alitaulukon summa.

Rajat

  • 1n1051 \le n \le 10^5
  • 1abn1 \le a \le b \le n
  • 109xi109-10^9 \le x_i \le 10^9

Esimerkki

Syöte:

8 2 4
-1 3 -2 8 -1 -1 -1 7

Tuloste:

9