指定した合計を持つ部分配列 (Subarrays of a given sum)
与えられた数列の中で、合計がちょうど
s になる部分配列がいくつ存在するかを調べたいとします。入力
最初の行には、配列の要素数である
n (1 ≤ n ≤ 1000) と、合計を示す数 s () の2つの整数が与えられます。続く行には、スペース区切りで n 個の整数 () が与えられ、それらが配列の要素を表します。出力
合計が
s になる部分配列の個数を一つの整数として出力してください。もし合計が s となる部分配列が存在しない場合は、0 を出力してください。例
Input | 入力 |
6 33
9 4 20 3 10 5 | 2 |
5 -10
10 2 -2 -20 10 | 3 |
説明
9 4 203 10 5,9 420 3 105
10 2 -2 -2010,102 -2 -20 10,10 2 -2-20 10
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB