Submit

Status

Ranklist

Back to Problems List

User's AC Ratio

74.2% (46/62)

Submission's AC Ratio

30.7% (93/303)

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

Sample Input 2

3 10
3 4 4

Sample Output 2

Sample Input 3

4 50
3 4 4 20

Sample Output 3

Sample Input 4

4 4
3 4 4 20

Sample Output 4

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