/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 366 点
問題文
高橋君は、お菓子屋さんで N 個のお菓子が一列に並んでいるのを見つけました。左から i 番目のお菓子の重さは W_i グラムです。
高橋君は、並んでいるお菓子の中から連続する 1 個以上のお菓子を選び、まとめて 1 つの袋に詰めて持ち帰ろうとしています。
お店には M 枚の袋が用意されており、j 番目の袋の耐荷重は C_j グラムです。袋に入れるお菓子の重さの合計が袋の耐荷重を超えると袋が破れてしまうため、お菓子の重さの合計は選んだ袋の耐荷重以下でなければなりません。
高橋君はできるだけ多くのお菓子を入れたいので、耐荷重が最も大きい袋を使おうとしましたが、あいにくその袋は売り切れていました。それどころか、耐荷重が大きい袋から順に売れてしまっていて、最終的に残っていたのは耐荷重が最も小さい袋だけでした。仕方がないので、高橋君はその袋を使うことにしました。
すなわち、高橋君が使う袋の耐荷重は C_{\min} = \min(C_1, C_2, \ldots, C_M) グラムです。
高橋君が袋を破らずにお菓子を持ち帰れるような、連続するお菓子の選び方が何通りあるか求めてください。具体的には、1 \leq l \leq r \leq N を満たす整数の組 (l, r) であって、
W_l + W_{l+1} + \cdots + W_r \leq \min(C_1, C_2, \ldots, C_M)
を満たすものの個数を求めてください。
制約
- 1 \leq N \leq 5 \times 10^5
- 1 \leq M \leq 5 \times 10^5
- 1 \leq W_i \leq 10^9 (1 \leq i \leq N)
- 1 \leq C_j \leq 10^{18} (1 \leq j \leq M)
- 入力はすべて整数
入力
N M W_1 W_2 \ldots W_N C_1 C_2 \ldots C_M
- 1 行目には、お菓子の個数を表す整数 N と、袋の枚数を表す整数 M が、スペース区切りで与えられる。
- 2 行目には、各お菓子の重さを表す整数 W_1, W_2, \ldots, W_N が、スペース区切りで与えられる。
- 3 行目には、各袋の耐荷重を表す整数 C_1, C_2, \ldots, C_M が、スペース区切りで与えられる。
出力
条件を満たす整数の組 (l, r) の個数を 1 行で出力せよ。
入力例 1
5 3 1 2 3 4 5 10 20 30
出力例 1
12
入力例 2
3 2 5 5 5 3 10
出力例 2
0
入力例 3
10 5 1 1 1 1 1 1 1 1 1 1 5 8 3 7 6
出力例 3
27
入力例 4
20 10 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4 100 50 30 80 25 60 45 70 35 55
出力例 4
83
入力例 5
1 1 1 1
出力例 5
1
Score : 366 pts
Problem Statement
Takahashi found N sweets lined up in a row at a candy shop. The weight of the i-th sweet from the left is W_i grams.
Takahashi wants to choose one or more consecutive sweets from the lineup, put them all into a single bag, and take them home.
The shop has M bags available, and the j-th bag has a weight capacity of C_j grams. Since a bag will tear if the total weight of the sweets inside exceeds its capacity, the total weight of the sweets must not exceed the capacity of the chosen bag.
Takahashi wanted to use the bag with the largest capacity so he could fit as many sweets as possible, but unfortunately that bag was sold out. In fact, the bags had been sold starting from the one with the largest capacity, and the only bag remaining was the one with the smallest capacity. Having no other choice, Takahashi decided to use that bag.
In other words, the capacity of the bag Takahashi uses is C_{\min} = \min(C_1, C_2, \ldots, C_M) grams.
Find the number of ways to choose consecutive sweets such that Takahashi can take them home without tearing the bag. Specifically, find the number of pairs of integers (l, r) satisfying 1 \leq l \leq r \leq N such that
W_l + W_{l+1} + \cdots + W_r \leq \min(C_1, C_2, \ldots, C_M)
Constraints
- 1 \leq N \leq 5 \times 10^5
- 1 \leq M \leq 5 \times 10^5
- 1 \leq W_i \leq 10^9 (1 \leq i \leq N)
- 1 \leq C_j \leq 10^{18} (1 \leq j \leq M)
- All inputs are integers
Input
N M W_1 W_2 \ldots W_N C_1 C_2 \ldots C_M
- The first line contains an integer N representing the number of sweets and an integer M representing the number of bags, separated by a space.
- The second line contains integers W_1, W_2, \ldots, W_N representing the weight of each sweet, separated by spaces.
- The third line contains integers C_1, C_2, \ldots, C_M representing the capacity of each bag, separated by spaces.
Output
Output the number of pairs of integers (l, r) satisfying the condition, on a single line.
Sample Input 1
5 3 1 2 3 4 5 10 20 30
Sample Output 1
12
Sample Input 2
3 2 5 5 5 3 10
Sample Output 2
0
Sample Input 3
10 5 1 1 1 1 1 1 1 1 1 1 5 8 3 7 6
Sample Output 3
27
Sample Input 4
20 10 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4 100 50 30 80 25 60 45 70 35 55
Sample Output 4
83
Sample Input 5
1 1 1 1
Sample Output 5
1