CSES - Alitaulukot
  • 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].