Submit Ranklist
Problem : 271 - Salesman
Problem Statistics
Solved Member:
7 Submission:
42 User Tried:
8 Statement:
有位旅行業務員發現，若要使用最佳化的方式規劃他在陸地上的旅行，那將會是一個十分難以處理的計算問題。因此他決定將他的生意轉向多瑙河 ( Danube River ) 沿岸的線性世界。他擁有一艘速度飛快的快艇，可以讓他沿著河從任何一個地點瞬間移動到另一個地點。遺憾的是，這艘快艇的油耗十分驚人。他在逆流時 ( 朝河流源頭的方向 ) ，每公尺移動將花費業務員 U 元，在順流時 ( 朝離開河流源頭的方向 ) ，每公尺移動將花費業務員 D 元。
河岸上共有N個貿易展是這個業務員所想參加的。每個貿易展為期一天。對於貿易展 X，業務員知道他的舉辦日期 TX，以及距離他購買快艇的日子為計算單位。他同時知道貿易展的舉辦地點是在河流源頭順流而下LX公尺處，以及如果參加這個貿易展，他所能得到的收入為MX元。他必須從他岸邊的住處開始和結束他的旅程，他的住處位於從河流源頭順流而下 S 公尺處。
請幫助這位旅行業務員規劃他應該選擇參加那些貿易展 ( 如果有要參加任何貿易展 ) 以及參加順序，使得他在旅程結束時能有最大的獲利。這位旅行業務員的獲利，指的是他因為參展所得到的收入總和，減去他在河流逆流與順流移動時的所有花費。
請記住如果貿易展 A 舉辦的時間在貿易展 B 之前，那麼業務員只能按照相同的順序參展 ( 亦即他不能先參加 B 再參加 A )。然而，如果兩個貿易展在同一天舉辦，這位業務員可以以任何順序參加這兩個貿易展。業務員一天內可以參加的貿易展數目並沒有限制，但他當然不能藉由參加相同的貿易展兩次而獲取兩次的收入。他可以路過他參加過的貿易展地點，但不會因此得到任何收入。
Task:
給定所有貿易展的日期、地點和可得到的收入，以及業務員河邊住家的位置和旅行的花費，請寫一個程式來計算他在旅程結束時，所可能得到的最大獲利。
Input:Output:
第一行依序含有整數N、U、D和S，中間用一個空白隔開。
接下來的N行描述這N個未按特定順序排序的貿易展。這N行中的第k行敘述第k個貿易展，含有三個以單一空白相間格的整數：貿易展的日期Tk、地點Lk以及業務員的收入Mk。
注意：輸入資料中所有的地點都不同。也就是說，沒有兩個貿易展會在相同地點舉行，同時也沒有貿易展的地點和業務員家的地點相同。
限制：
1 ≤ N ≤ 500000，貿易展數目。
1 ≤ D ≤ U ≤ 10，每一公尺逆流(U)和順流(D)的花費。
1 ≤ S ≤ 500001，業務員的住家位置。
1 ≤ Tk ≤ 500000，貿易展k的舉行日期。
1 ≤ Lk ≤ 500001，貿易展k的位置。
1 ≤ Mk ≤ 4000，業務員若參加貿易展k所能得到的收入。
輸出含有一個整數的一行，這個整數為業務員在旅程結束時所能得到的獲利最大值。
Sample Input:Sample Output:
4 5 3 100
2 80 100
20 125 130
10 75 150
5 120 110
50
HINT:
最佳的排成方法為參加貿易展 1 和 3 ( 位於地點 80 和 75 ) 。所有事件的收入和花費如下：
•業務員逆流旅行20公尺，花費100元。截至目前為止獲利：-100
•他參加貿易展1，收入100。截至目前為止獲利：0
•他逆流旅行5公尺，花費25元。截至目前為止獲利：-25
•他參加貿易展3，收入150元。截至目前為止獲利：125
•他順流旅行25公尺回到家，花費75元。最後結算獲利：50
評分資訊：
佔總分60分的測試資料中，沒有兩個貿易展會在同一天舉辦。
佔總分40分的測試資料中，所有輸入資料中的數字都不會超過5000。
同時滿足上面兩個條件的測試資料，佔總分的15分。
滿足上面兩個條件中至少一個條件的測試資料，佔總分的85分。
Source:
IOI 2009
Problem Setter
hanhan0912 Testdata:
| Test | Time | Memory | Score |
|---|
| 0 | 1000ms | 131072kb | |
| 1 | 3000ms | 131072kb | 2 |
| 2 | 3000ms | 131072kb | 3 |
| 3 | 3000ms | 131072kb | 4 |
| 4 | 3000ms | 131072kb | 3 |
| 5 | 3000ms | 131072kb | 3 |
| 6 | 3000ms | 131072kb | 2 |
| 7 | 3000ms | 131072kb | 4 |
| 8 | 3000ms | 131072kb | 4 |
| 9 | 3000ms | 131072kb | 5 |
| 10 | 3000ms | 131072kb | 5 |
| 11 | 3000ms | 131072kb | 5 |
| 12 | 3000ms | 131072kb | 5 |
| 13 | 3000ms | 131072kb | 5 |
| 14 | 3000ms | 131072kb | 3 |
| 15 | 3000ms | 131072kb | 3 |
| 16 | 3000ms | 131072kb | 4 |
| 17 | 3000ms | 131072kb | 2 |
| 18 | 3000ms | 131072kb | 3 |
| 19 | 3000ms | 131072kb | 5 |
| 20 | 3000ms | 131072kb | 2 |
| 21 | 3000ms | 131072kb | 3 |
| 22 | 3000ms | 131072kb | 3 |
| 23 | 3000ms | 131072kb | 3 |
| 24 | 3000ms | 131072kb | 4 |
| 25 | 3000ms | 131072kb | 2 |
| 26 | 3000ms | 131072kb | 3 |
| 27 | 3000ms | 131072kb | 2 |
| 28 | 3000ms | 131072kb | 3 |
| 29 | 3000ms | 131072kb | 2 |
| 30 | 3000ms | 131072kb | 3 |