Submit Ranklist
Problem : 328 - Machine Works
Problem Statistics
Solved Member:
4 Submission:
27 User Tried:
4 Statement:
你開了一家公司Arbitrarily Complex Machines(以ACM簡稱)，身為一個企業家，你的目標是在一定天數內賺很多錢，在這段時間內你可以購賣或賣出機器或是利用機器產生獲利！基於空間不夠大，ACM一天最多只能擁有一台機器。
在這段時間內，可能會有很多機器可以購買，一個價錢Pi的機器Mi只能在第Di天購買，如果不在第Di天買，他將會被其他人買走，但如果ACM沒有足夠的錢，ACM將無法購買此機器。
如果你在第Di天買購買機器Mi，ACM可以在第Di + 1天開始每天產生獲利Gi給公司。
你可以在購買機器Mi後的任何一天販賣他並獲得Ri元，而在你賣掉的那天他將不會產生獲利，但你可以在同一天購買一台新的機器。
當規定天數過後，ACM會賣掉手上擁有的機器，你的任務是找出最大獲利。
Input:Output:
輸入可能有多筆測試資料，對於每筆測試資料的第一行有N C D，其中N(1 ≤ N ≤ 100000)為可購買的機器總數量，C(1 ≤ C ≤ 109)為一開始ACM所擁有的錢數，D(1 ≤ D ≤ 109)為規定時間的天數。
接下來會有N行，每行四個數字Di Pi Ri Gi，分別表示機器Mi的販賣天數、購入價錢、賣出價錢、每日獲利，其中1 ≤ Di ≤ D，1 ≤ Ri < Pi ≤ 109，1 ≤ Gi ≤ 109。
測試檔案的最後一行會以三個0表示檔案結束(即N=C=D=0時結束)。
對於每筆測試資料輸出在第D+1天時ACM的能擁有的最大錢數。
Sample Input:Sample Output:
6 10 20
6 12 1 3
1 9 1 2
3 2 1 2
8 20 5 4
4 11 7 4
2 10 9 1
0 0 0
Case 1: 44
Source:
ICPC World Final 2011
Problem Setter
hanhan0912 Testdata:
| Test | Time | Memory | Score |
|---|
| 0 | 1000ms | 65536kb | |
| 1 | 5000ms | 65536kb | 100 |