2194 . B. 掃地機器人
TopCoder
Tags
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
$answer$
- $answer$：為一整數，代表 $m$ 分鐘內掃地機器人能掃除最多的灰塵量。
Sample Input 1
0 0 0
3 1 6 3
1 0 3 2
Sample Output 1
Sample Input 2
1 1 6
3 1 6 3
1 0 3 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 |