1306 已加強測資並 rejudge

Submit

Status

Discussion / Solution

Ranklist

Back to Problems List

TopCoder

Caido

$W aimai \sim$

User's AC Ratio

63.0% (87/138)

Submission's AC Ratio

21.9% (161/734)

Description

大麥集團最近研發了新式的掃地機器人，可利用歷史資料（如特定區域過往的平均髒亂程度、地面材質是否容易清掃等）來增加掃除工作的效率。今有 $n$ 間位於同一走廊的教室需要打掃，這些教室由左而右分別編號為 $1$ 至 $n$ ，每間教室的髒亂程度各有不同。如下圖為一 $n = 4$ 的例子：

掃地機器人因掃除力有限，因此對於同一間教室可能需要反覆多次的清掃才能將該教室掃除乾淨。在進行掃除時，剛開始因為灰塵較多比較容易吸除，但隨著掃除的時間增加，剩下的灰塵會愈來愈難被吸除。為了簡化問題，我們假設機器人在同一間教室必須打掃整數分鐘的時間，並且每分鐘能吸除的灰塵量會隨時間線性遞減，減至 $0$ 則不會再減少。更詳細地說，對於教室 $i$ 會有兩個參數 $s_{i}$ 及 $d_{i}$ ， $s_{i}$ 為此教室掃除第一分鐘能吸到的灰塵量，而 $d_{i}$ 則代表每隔一分鐘能吸到灰塵的遞減量。因此，掃地機器人在教室 $i$ 清掃的第 $x$ 分鐘能吸到的灰塵量為 $max {s_{i} - d_{i} \cdot (x - 1), 0}$ 。

今天有 $m$ 分鐘的時間供大麥掃地機器人進行打掃，在這 $m$ 分鐘內機器人可以自由往返及打掃各教室。假設大麥掃地機器人一開始位於教室 $1$ 。給定每間教室第 $1$ 分鐘能吸除的灰塵量、單位時間的遞減量以及相鄰兩間教室移動所需的時間，請幫大麥掃地機器人計算最多可吸除的灰塵量。

Input Format

$n m$
$t_{1} t_{2} \dots t_{n - 1}$
$s_{1} s_{2} \dots s_{n}$
$d_{1} d_{2} \dots d_{n}$

$n$ 、 $m$ ：依序為教室數及可打掃的時間（單位分鐘）。
$t_{i}$ ：掃地機器人從教室 $i$ 移動到教室 $i + 1$ 的時間（單位分鐘）。
$s_{i}$ ：掃地機器人在教室 $i$ 的第 $1$ 分鐘能吸到的灰塵量。
$d_{i}$ ：掃地機器人在教室 $i$ 每分鐘能吸到的灰塵遞減量。

Output Format

$a n s w e r$

$a n s w e r$ ：為一整數，代表 $m$ 分鐘內掃地機器人能掃除最多的灰塵量。

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

Hints

測資限制

$1 \leq n \leq 1000$ 。
$1 \leq m \leq 10^{9}$ 。
$0 \leq t_{i} \leq 10^{9}$ 。（ $i \in {1, 2, \dots, n - 1}$ ）
$1 \leq s_{i} \leq 10^{9}$ 。（ $i \in {1, 2, \dots, n}$ ）
$0 \leq d_{i} \leq 10^{9}$ 。（ $i \in {1, 2, \dots, n}$ ）

評分說明
本題共有二組子任務，條件限制如下所示。每一子任務可有一或多筆測試資料，該組所有測試資料皆需答對才會獲得該組分數。

(30%) $m \leq 1000$ 。
(70%) 無額外限制。

範例解釋
第二筆範例中，機器人可以依照以下策略清掃到最多的灰塵：

第 $1$ 到第 $2$ 分鐘末：在教室 $1$ 清掃，得到 $3 + 2 = 5$ 單位灰塵。
第 $3$ 分鐘：從教室 $1$ 移動到教室 $2$ 。
第 $4$ 到第 $6$ 分鐘末：在教室 $2$ 清掃，得到 $1 + 1 + 1 = 3$ 單位灰塵。
第 $7$ 分鐘：從教室 $2$ 移動到教室 $3$ 。
第 $8$ 到第 $9$ 分鐘末：在教室 $3$ 清掃，得到 $6 + 3 = 9$ 單位灰塵。
以上 $9$ 分鐘，共蒐集到 $5 + 3 + 9 = 17$ 單位的灰塵。

Problem Source

2021 TOI 入營考 pB
testdata set by Omelet

Subtasks

No.	Testdata Range	Constraints	Score
1	0~14	$m \leq 1000$	30
2	0~49	無額外限制	70

Testdata and Limits

No.	Time Limit (ms)	Memory Limit (VSS, KiB)	Output Limit (KiB)	Subtasks
0	500	524288	65536	1 2
1	500	524288	65536	1 2
2	500	524288	65536	1 2
3	500	524288	65536	1 2
4	500	524288	65536	1 2
5	500	524288	65536	1 2
6	500	524288	65536	1 2
7	500	524288	65536	1 2
8	500	524288	65536	1 2
9	500	524288	65536	1 2
10	500	524288	65536	1 2
11	500	524288	65536	1 2
12	500	524288	65536	1 2
13	500	524288	65536	1 2
14	500	524288	65536	1 2
15	500	524288	65536	2
16	500	524288	65536	2
17	500	524288	65536	2
18	500	524288	65536	2
19	500	524288	65536	2
20	500	524288	65536	2
21	500	524288	65536	2
22	500	524288	65536	2
23	500	524288	65536	2
24	500	524288	65536	2
25	500	524288	65536	2
26	500	524288	65536	2
27	500	524288	65536	2
28	500	524288	65536	2
29	500	524288	65536	2
30	500	524288	65536	2
31	500	524288	65536	2
32	500	524288	65536	2
33	500	524288	65536	2
34	500	524288	65536	2
35	500	524288	65536	2
36	500	524288	65536	2
37	500	524288	65536	2
38	500	524288	65536	2
39	500	524288	65536	2
40	500	524288	65536	2
41	500	524288	65536	2
42	500	524288	65536	2
43	500	524288	65536	2
44	500	524288	65536	2
45	500	524288	65536	2
46	500	524288	65536	2
47	500	524288	65536	2
48	500	524288	65536	2
49	500	524288	65536	2

Submit

2194 . B. 掃地機器人

TopCoder

User's AC Ratio

Submission's AC Ratio

Tags

Description

Input Format

Output Format

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

Hints

Problem Source

Subtasks

Testdata and Limits

2194 . B. 掃地機器人

TopCoder

User's AC Ratio

Submission's AC Ratio

Tags Show solution-related tags

Description

Input Format

Output Format

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

Hints

Problem Source

Subtasks

Testdata and Limits

Tags