723 . 打工仔

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

aacpschool

User's AC Ratio

75.0% (3/4)

Submission's AC Ratio

75.0% (3/4)

Tags

apcsc apcsc-greedy

Description

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

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

Input Format

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

  • 0≤T,n,Mi,Di,ti≤105
  • nT≤107

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 ti=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