Windows Reaching the Target

Difficulty: 1300 3000 ms 128 MB

sliding-window

Count how many contiguous windows of exactly K elements have a sum of at least T.

Input: the first line has N, K and T; the second line has N integers.

Output: the number of windows with sum ≥ T.

Constraints:

• 1 ≤ K ≤ N ≤ 10⁵
• −50 ≤ a_i ≤ 50
• |T| ≤ 5×10⁶

Sample Tests

5 2 4
1 3 2 4 1

4

2 1 0
-1 1

1

Read the Editorial