- Time limit: 1.00 s
- Memory limit: 512 MB
Sinulle on annettu taulukko, jossa on n lukua, sekä tavoiteluku x.
Monellako tavalla voit valita taulukosta epätyhjän yhtenäisen alitaulukon, jonka lukujen summa on x?
Syöte
Syötteen ensimmäisellä rivillä on kaksi kokonaislukua n ja x: taulukon koko ja tavoiteluku.
Seuraavalla rivillä on n kokonaislukua t_1,t_2,\ldots,t_n: taulukon sisältö.
Tuloste
Tulosta yksi kokonaisluku: vastaus tehtävään.
Rajat
- 1 \le n \le 5 \cdot 10^5
- -10^9 \le x \le 10^9
- -10^9 \le t_i \le 10^9
Esimerkki
Syöte:
12 9 1 2 3 4 5 6 7 8 9 10 11 12
Tuloste:
3
Selitys: Alitaulukot ovat [2,3,4], [4,5] ja [9].