nrsec

Nrsec

== include(page="template/taskheader" task_id="nrsec") ==

Poveste şi cerinţă...

Electra se pregateste pentru olimpiada de informatica. De curand a dat peste urmatoarea problema. Se da un sir de $N$ numere intregi si un numar natural $K$. Se cere cel mai mic numar intreg $S$ astfel incat numarul de subsecvente a caror suma este mai mica sau egala cu $S$ sa fie cel putin $K$. Rezolvati problema ca apoi sa ii puteti da un "hint" Electrei despre cum se rezolva. Daca o ajutati, Electra va va rasplati cum poate ea mai bine.

h2. Date de intrare

Fişierul de intrare $nrsec.in$ ...

Fişierul de intrare $nrsec.in$ va contine pe prima linie numerele $N$ si $K$. Urmatoarea linie contine sirul de $N$ numere intregi separate prin spatii.

h2. Date de ieşire

În fişierul de ieşire $nrsec.out$ ...

În fişierul de ieşire $nrsec.out$ veti afisa numarul $S$ ce respecta cerinta de mai sus.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 10^5^$
* $1 ≤ K ≤ N * (N + 1) / 2$
* Modulul numerelor din sir nu va depasi valoarea $10^9^$
* Suma unei subsecvente este suma elemetelor continute in acea subsecventa
 

h2. Exemplu
table(example). |_. nrsec.in |_. nrsec.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 4 5
4 -2 3 -1
| 2

|
h3. Explicaţie

...

Sumele tuturor subsecventelor sunt : $4,2,5,4,-2,1,0,3,2,-1$. Se observa ca $6$ dintre acestea sunt mai mici sau egale cu $2$. Deci $2$ este raspunsul ce reprezinta cel mai mic numar intreg astfel incat exista cel putin $5$ subsecvente a caror suma este mai mica sau egala cu $2$.

== include(page="template/taskfooter" task_id="nrsec") ==

3567