User's AC Ratio

73.3% (44/60)

Submission's AC Ratio

31.0% (90/290)

Description

彩彩喜歡劈瓦,所以每天都有一定數量的瓦要劈

不過劈多劈少要看狀況而定,所以有個值叫手感值 $P$ (我喜歡叫修瓦值就是了)

每天有 $a$ 份瓦,要是 $P > 0$ 就可以去劈瓦
$P \ge a$ 就能把當天的瓦都劈掉,$P$ 會減去 $a$
$P < a$ 照樣能劈,但就會直接把手感值 $P$ 用光
(也就是當天瓦可能劈不完,視 $P$ 的大小而定)

例如目前 $P = 8$
今天有 $5$ 個瓦,那決定劈的話 $P$ 就剩 $3$,共劈 $5$ 個瓦
今天有 $9$ 個瓦,那決定劈的話 $P$ 就剩 $0$,共劈 $8$ 個瓦

而當天彩彩也可以休息不去劈瓦,這天結束手感值 $P$ 會加上 $a$
但彩彩再怎麼強也是人,所以 $P$ 有個上限 $L$,且第一天開始前 $P$ 為 $0$

給定 $n$ 天的劈瓦行程表,求最大的劈瓦數

Input Format

第一行給定 $n, L \space (1 \le n, L \le 3000)$ 表示共幾天要劈瓦以及手感值的上限。
第二行有 $n$ 個正整數 $ a_1, a_2, a_3, \cdots , a_i, \cdots , a_n $,$a_i$ 代表第 $ i $ 天有幾份瓦能劈 $ (0 \le a_i \le 10^ 5 ) $。

Output Format

輸出彩彩最多能夠劈多少瓦

Sample Input 1

4 100
6 8 7 4

Sample Output 1

11

Sample Input 2

3 10
3 4 4

Sample Output 2

4

Sample Input 3

4 50
3 4 4 20

Sample Output 3

11

Sample Input 4

4 4
3 4 4 20

Sample Output 4

7

Hints

範測 2 說明
以下 sum 代表第一天到目前總共劈了多少瓦

第 1 天一定得去休息,所以該天結束後 $P = 3$

第 2 天有 $P > 0$ 了,可以開始考慮劈瓦 (彩黑)
若該天去劈瓦,那麼 $P = 0$,$\text{sum} = 3$
如果不去劈瓦,那麼 $P = 7$,$\text{sum} = 0$

第 3 天要劈瓦的話那要 $P > 0$,
所以從前一天來看,不去劈瓦的話才有可能
若昨天不劈今天劈,$P = 3$,$\text{sum} = 4$

所以劈瓦行程表應該要訂:不劈,不劈,劈,最多能劈 $4$ 片。



彩彩好可愛
PIXIV:79504151

Problem Source

Subtasks

No. Testdata Range Score
1 0~33 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 262144 65536 1
1 1000 262144 65536 1
2 1000 262144 65536 1
3 1000 262144 65536 1
4 1000 262144 65536 1
5 1000 262144 65536 1
6 1000 262144 65536 1
7 1000 262144 65536 1
8 1000 262144 65536 1
9 1000 262144 65536 1
10 1000 262144 65536 1
11 1000 262144 65536 1
12 1000 262144 65536 1
13 1000 262144 65536 1
14 1000 262144 65536 1
15 1000 262144 65536 1
16 1000 262144 65536 1
17 1000 262144 65536 1
18 1000 262144 65536 1
19 1000 262144 65536 1
20 1000 262144 65536 1
21 1000 262144 65536 1
22 1000 262144 65536 1
23 1000 262144 65536 1
24 1000 262144 65536 1
25 1000 262144 65536 1
26 1000 262144 65536 1
27 1000 262144 65536 1
28 1000 262144 65536 1
29 1000 262144 65536 1
30 1000 262144 65536 1
31 1000 262144 65536 1
32 1000 262144 65536 1
33 1000 262144 65536 1