1921 . 吐鈔機2

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

baluteshih

User's AC Ratio

86.4% (70/81)

Submission's AC Ratio

24.1% (169/701)

Tags

CKsim 2016-CKsim-5th acm 2011-ACM

Description

有一天你透過某種神秘力量找到了黑魔法地下市場。你赫然發現在這個市場上竟然有大量的吐鈔機在流通，所以你打算做個好計畫，準備在接下來的D+1天內大賺一筆。

這個黑魔法地下市場的吐鈔機販賣部，在09:00-10:00會提供收購二手吐鈔機的服務，而19:00-20:00則提供販賣新吐鈔機的服務。
你透過強大的黑魔法力量得知了接下來將會販賣的新吐鈔機資訊。對於第i種吐鈔機，它只要在某一天有任何一個時間開著，它這天就會吐出Gi元的鈔票。而它會在第Di天以Pi元的價格販賣，由於吐鈔機的生意都很好，過了這一天之後就再也買不到這種吐鈔機了。魔法世界裡是沒有銀行的，所以你絕對沒辦法跟別人貸款，自己有多少錢就只能買多少錢的吐鈔機。
當然，你也調查了二手市場的行情，得知第i種吐鈔機的二手轉售價格是Ri。當然，二手收購價一定比原價還要低。

然而，吐鈔機的運作有幾個限制：吐鈔機只能在10:00-19:00期間運作，而且一個人在一個時刻只能擁有一臺吐鈔機，否則黑魔法力量會互相干擾，把所有的錢全部變成廢紙。

你在第1天09:00的時候有C元本金，接下來只能靠吐鈔機賺錢。求在第D+1天10:00的時候，你最多可以擁有多少錢。

Input Format

第一行有三個正整數N,C,D，分別代表吐鈔機的種類數、你一開始擁有的本金和你打算在這個市場裡交易多久。
接下來N行，每行有四個正整數Di,Pi,Ri,Gi，代表第i臺吐鈔機的資訊。關於它們的意義，請參照題敘。

因為這是個魔法題，為了順利作答，你可能會需要用到__int128的黑魔法。這是範圍在[−2127,2127)的整數型別，由g++提供。使用這個型別不需要引入任何標頭檔。這個型別不能直接cin/cout/printf/scanf，但是可以轉型成一般的整數型別。
當然，並不一定必須用到這個黑魔法才能解開這個魔法題。

對於所有的測資，N≤105；C,D,Gi≤109；Di≤D；Ri<Pi≤109。

子任務（測資） 額外限制 分數
1 (0~7) N≤20 9
2 (0~9) N≤300 12
3 (0~12) N≤1000 13
4 (0~15) N≤104 25
5 (0~19) 無 41

Output Format

輸出一行包含一個正整數，代表在第D+1天10:00的時候，你最多可以擁有多少錢。

Sample Input 1

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

Sample Output 1

44

Hints

對於範例測資：
在第3天的時候買進第3種吐鈔機，此時剩8元；
在第6天的時候賣掉，此時有13元；買進第1種吐鈔機，剩1元；
到第21天的時候賣掉，總共得到44元。

Problem Source

建國中學105學年度校內第五次模擬賽pD

Subtasks

No. Testdata Range Score
1 0~7 9
2 0~9 12
3 0~12 13
4 0~15 25
5 0~19 41

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 900 65536 262144 1 2 3 4 5
1 900 65536 262144 1 2 3 4 5
2 900 65536 262144 1 2 3 4 5
3 900 65536 262144 1 2 3 4 5
4 900 65536 262144 1 2 3 4 5
5 900 65536 262144 1 2 3 4 5
6 900 65536 262144 1 2 3 4 5
7 900 65536 262144 1 2 3 4 5
8 900 65536 262144 2 3 4 5
9 900 65536 262144 2 3 4 5
10 900 65536 262144 3 4 5
11 900 65536 262144 3 4 5
12 900 65536 262144 3 4 5
13 900 65536 262144 4 5
14 900 65536 262144 4 5
15 900 65536 262144 4 5
16 400 65536 262144 5
17 400 65536 262144 5
18 400 65536 262144 5
19 400 65536 262144 5
Submit
Back to Top