4533 . B2. 姜姜不想驗b7 (Seven)
Description
Input Format
$n, k$
$a_0 \;\; a_1 \;\; a_2 \;\; ... \;\; a_{n-1}$
$n$ 代表總共有 $n$ 小時
而姜姜最早可以在 0點整 的時候上線，最晚 $n$點整 時一定要下線
接下來一行整數中，$a_i$ 代表從 $i$ 點整 到 $(i+1)$ 點整 之間會上線催姜姜驗b7幾次
保證 $n, k, a_i$ 皆為非0整數
$1 \le a_i < 2 ^ {31}$
$0 < k \le \sum a_i$
Output Format
求出總共有多少個(上線, 下線)區間，使得姜姜不會被鹽亞倫催驗題超過$k$次
Sample Input 1
5 5
1 1 1 1 1
1 1 1 1 1
Sample Output 1
15
Sample Input 2
5 5
1 2 3 4 5
1 2 3 4 5
Sample Output 2
7
Sample Input 3
5 5
1 1 1 1 1
1 1 1 1 1
Sample Output 3
15
Hints
雖然我不是 $\text{cheissmart}$，但去寫B7聽起來不錯，對吧？
這題其實是這次上機考的第七題
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~9 | $1 \le n\le 1000$ | 11 |
| 2 | 0~19 | $1 \le n\le 5\times10 ^ 5$ | 42 |
| 3 | 0~34 | $1 \le n\le 5\times10 ^ 7$ | 47 |
