723 . 打工仔

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

1xlc

User's AC Ratio

100.0% (1/1)

Submission's AC Ratio

100.0% (1/1)

Tags

apcsc apcsc-greedy

Description

魯夫的夢想是成為航海王，但長榮跌下來以後他就跟身邊的韭菜一樣被割了，現在只能睡公園的紙箱。
為了重新找回他的夢想，他要打一些奇怪的工籌措資金。
因為公園不好睡，魯夫每天打完工以後他會直接在打工的地點過夜。
現在有 $n$ 間公司可以給魯夫打工且這些公司在同一條直線上，公司由近到遠編號 $1, 2, 3, \ldots, n$，並且從公園到第一間公司需要花 $t_1$ 天時間，從第 $i-1$ 間公司到第 $i$ 間公司需要花 $t_i$ 天時間。

而這些公司特別黑心，會紀錄魯夫總共來了幾天然後依據這個次數扣他的薪水。假設第 $i$ 個公司給你的初始薪水是 $M_i$，他在此公司工作第 $i$ 天時只會給你 $M_i - (i - 1)\cdot D_i$ 的薪水。請你幫魯夫算一下他在 $T$ 天之內最多可以賺到多少錢？

Input Format

輸入第一行有兩個整數 $T, n$，第二行有 $n$ 個整數 $M_i$，第三行有 $n$ 個整數 $D_i$，第四行有 $n$ 個整數 $t_i$。整數之間以空白分隔。其中保證：

  • $0 \leq T, n, M_i, D_i, t_i \leq 10^ 5$
  • $nT \leq 10^ 7$

Output Format

輸出魯夫在第 $T$ 天能賺到的錢的最大值。

Sample Input 1

12 2
10 1
2 5
0 2

Sample Output 1

31

Sample Input 2

48 4
10 15 20 17
0 3 4 3
0 1 2 3

Sample Output 2

480

Hints

Problem Source

TIOJ 1399

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 2~10 $t_i=0$ 20
3 0~29 無額外限制 80

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 3
1 1000 524288 65536 1 3
2 1000 524288 65536 2 3
3 1000 524288 65536 2 3
4 1000 524288 65536 2 3
5 1000 524288 65536 2 3
6 1000 524288 65536 2 3
7 1000 524288 65536 2 3
8 1000 524288 65536 2 3
9 1000 524288 65536 2 3
10 1000 524288 65536 2 3
11 1000 524288 65536 3
12 1000 524288 65536 3
13 1000 524288 65536 3
14 1000 524288 65536 3
15 1000 524288 65536 3
16 1000 524288 65536 3
17 1000 524288 65536 3
18 1000 524288 65536 3
19 1000 524288 65536 3
20 1000 524288 65536 3
21 1000 524288 65536 3
22 1000 524288 65536 3
23 1000 524288 65536 3
24 1000 524288 65536 3
25 1000 524288 65536 3
26 1000 524288 65536 3
27 1000 524288 65536 3
28 1000 524288 65536 3
29 1000 524288 65536 3
Submit
Back to Top