8 . 彩彩劈瓦

Submit
Status
Ranklist
Back to Problems List

User's AC Ratio

73.8% (45/61)

Submission's AC Ratio

30.2% (91/301)

Tags

2020 高階競技程式設計 - 課前賽

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
Submit
Status
Ranklist
Back to Top