4533 . B2. 姜姜不想驗b7 (Seven)

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

餘切
$\Huge\text{freeh1}$

User's AC Ratio

88.9% (8/9)

Submission's AC Ratio

45.0% (18/40)

Tags

111學術上機考 學術上機考

Description

姜姜喜歡待在 DC 語音，鹽亞倫喜歡火車
但因為鹽亞倫不會寫p7，於是鹽亞倫出了一題b7
姜姜用立葉的魔法得知了鹽亞倫接下來每個小時會上線催他驗題幾次
鹽亞倫要是上線了然後發現姜姜也在線上就會去催姜姜幫他驗 b7
姜姜想要選擇一段連續的時段掛在語音，但是他不想被催驗 b7 太多次，所以他訂下一個限制：從他上線到下線的這段時間，不能讓鹽亞倫催他超過 $k$ 次。

已知接下來每個小時內鹽亞倫會上線催他驗題幾次
並且姜姜都是在整點時上線和下線
請幫姜姜算出，他可以有幾種連續的(上線, 下線)時間對
使得他在線上的這段時間鹽亞倫催他的次數不超過 $k$ 次。

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

Sample Output 1

15

Sample Input 2

5 5
1 2 3 4 5

Sample Output 2

7

Sample Input 3

5 5
1 1 1 1 1

Sample Output 3

15

Hints

雖然我不是 $\text{cheissmart}$，但去寫B7聽起來不錯，對吧？
這題其實是這次上機考的第七題

Problem Source

111學年度建北電資指定科目考試【資訊科上機考】
※ Statement modified from TIOJ

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

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2200 250000 65536 1 2 3
1 2200 250000 65536 1 2 3
2 2200 250000 65536 1 2 3
3 2200 250000 65536 1 2 3
4 2200 250000 65536 1 2 3
5 2200 250000 65536 1 2 3
6 2200 250000 65536 1 2 3
7 2200 250000 65536 1 2 3
8 2200 250000 65536 1 2 3
9 2200 250000 65536 1 2 3
10 2200 250000 65536 2 3
11 2200 250000 65536 2 3
12 2200 250000 65536 2 3
13 2200 250000 65536 2 3
14 2200 250000 65536 2 3
15 2200 250000 65536 2 3
16 2200 250000 65536 2 3
17 2200 250000 65536 2 3
18 2200 250000 65536 2 3
19 2200 250000 65536 2 3
20 2200 250000 65536 3
21 2200 250000 65536 3
22 2200 250000 65536 3
23 2200 250000 65536 3
24 2200 250000 65536 3
25 2200 250000 65536 3
26 2200 250000 65536 3
27 2200 250000 65536 3
28 2200 250000 65536 3
29 2200 250000 65536 3
30 2200 300000 65536 3
31 2200 250000 65536 3
32 2200 250000 65536 3
33 2200 250000 65536 3
34 2200 250000 65536 3
Submit
Back to Top