- Time limit: 1.00 s
- Memory limit: 128 MB
Tehtäväsi on jakaa taulukko yhtenäisiin väleihin niin, että jokaisen välin lukujen summa on enintään $k$. Mikä on pienin mahdollinen välien määrä?
Syöte
Syötteen ensimmäisellä rivillä on luvut $n$ ja $k$.
Syötteen toinen rivi sisältää $n$ lukua $x_1,x_2,\ldots,x_n$: taulukon sisältö.
Mikään taulukon luku ei ole suurempi kuin $k$.
Tuloste
Ohjelmasi tulee tulostaa yksi kokonaisluku: pienin välien määrä.
Rajat
- $1 \le n \le 10^5$
- $1 \le x_i \le 10^9$
- $1 \le k \le 10^{18}$
Syöte:
8 5
2 2 2 1 3 1 2 1
Tuloste:
3
Selitys: Jako on seuraava: "2 | 2 2 1 | 3 1 | 2 1". Huomaa, että yksi ryhmistä jatkuu taulukon lopusta alkuun.