1448 . 下午茶與內耗
TopCoder
Tags
Description
在大道上有 $N$ 個飯店，住著有錢的花花與他的朋友們。花花是個很會自己躲起來內耗的人，有點奇異地，他也很喜歡參加聚會和旅行。
接下來的 $T$ 天內，有其中 $M$ 天會有恰好一場好友們間的聚會。稍微更具體，在第 $t_i$ 天下午的第 $x_i$ 個飯店的餐廳會有一個下午茶聚會，大家會閒話家常，花花可以自由選擇參加或不參加（不來也沒人在乎，真假）。
如果花花選擇參加的話，假設他從第 $X$ 間飯店出發參加，他首先會因為旅行很快樂，而增加 $K \times \mid X-x_i \mid$ 心情值；又因為聚會中會得到情緒價值，心情值會改變 $a_i$（因為可能感到更加空虛，所以可以是負的）；最後，在聚會中和大家交流後，花花會更新心中對朋友們的崇拜程度以及他複雜的價值觀，而將內耗程度 $B$ 改成 $b_i$。當然，有聚會也不一定要參加。
如果花花選擇不參加聚會或著本來當天就沒有聚會的話，他會待在原本的飯店，窩在房間裡滑短影音、吃泡麵、打電動，然後下午想到自己真的很廢就會開始內耗，心情值會降低內耗程度 $B$。
有全知視角的你，知道花花一開始（第 $0$ 天的晚上、第 $1$ 天的早上）的心情值是 $0$ 以及內耗程度 $B$ 為 $B_0$ 還有將會發生的所有聚會的資訊，你還知道他一開始可以住在任何一家飯店。請告訴可憐的花花，他在做出最佳規劃的情況下，第 $T$ 天晚上睡前的心情值最高可以是多少吧！
Input Format
第一行有五個整數 $N, M, T, K, B_0。$
接下來 $M$ 行各自代表一個聚會，每行都有四個整數，分別為 $t_i, x_i, a_i, b_i$。
- $1 \leq N \leq 5\times 10^ 5$
- $1 \leq M \leq T \leq 5\times 10^ 5$
- $0 \leq K \leq 10^ 6$
- $-10^ {12} \leq a_i \leq 10^ {12}$
- $1 \leq b_i, B_0 \leq 10^ {12}$
- $1 \leq t_i \leq T$
- $1 \leq x_i \leq N$
- $\forall 1<i \leq M, t_{i-1} < t_i$
Output Format
請輸出一個整數，代表花花在第 $T$ 天，心情值能達到的最大值。
Sample Input 1
8 6 9 1 5 2 3 10 7 3 6 -5 2 5 3 8 9 6 7 12 3 7 3 -4 1 9 8 15 6
Sample Output 1
52
Sample Input 2
5000 12 5000 1 188207685612 180 2720 798781461350 281340656798 1237 1439 -912201725416 551708091421 1239 2351 201815771763 804859804911 1425 1645 -65937847 111159945632 2129 4480 21428903709 581056030582 2991 1443 98131083188 543492293164 3842 4361 534524015296 897028263851 4092 276 874050046092 409251171437 4160 952 -293543213700 274962177258 4525 2004 -986265641624 715207523596 4567 1246 137016508277 371597351439 4942 3303 -928735342712 173871512659
Sample Output 2
-665404615880380
Sample Input 3
5000 8 5000 9 172000236799 523 4491 840864638788 491214620680 791 1531 721463785952 353544881194 1630 1011 312335842962 336590966766 2278 1927 597459820423 106782778395 2307 3601 -545480048465 968902289578 2315 3180 -535569406518 765306736594 2632 542 -840573186381 985525883841 3555 408 -526168780545 679107471745
Sample Output 3
-681709802134433
Sample Input 4
100000 7 100000 0 77117776485 13246 37314 -871810571063 421928975273 33866 43196 278428518315 180863798788 34934 8366 -810880319191 336655551254 39162 37445 274360918798 833520411797 40094 92389 279968366889 869894840104 60984 32241 -120870968056 529075242717 87262 60073 -110526830054 394071975080
Sample Output 4
-7711777648500000
Hints
為了方便理解題目，以下為對於範例一的其中一個規劃的解釋。在這個規劃中，第 $T$ 天的睡前心情值為 $22$，而非 $52$，並非最佳。
第零天的時候住在飯店 $7$，內耗程度為 $5$，晚上睡前心情值為 $0$。
第一天在飯店 $7$ 滑 reels，內耗程度依然為 $5$，睡前心情值為 $-5$。
第二天去飯店 $3$ 參加聚會，感覺融入不了話題。心情變更差，心情值變成 $-5 + 1\times | 3-7 | -5 = -6$，內耗程度則改變成 $2$。
第三、四天在飯店 $3$ 把 K-ON！動畫刷了第十次，睡前心情值分別為 $-8, -10$。內耗程度依然為 $2$。
第五天又參加了在飯店 $3$ 的聚會，感覺挺好，心情值變成 $-10 + 1\times | 3 - 3 | + 8 = -2$，內耗程度變成 $9$。
第六天參加了在飯店 $7$ 的聚會，心情值變成 $-2 + 1\times | 3 - 7 | + 12 = 14$，內耗程度變為 $3$。
第七、八天在飯店 $7$ 睡大覺，睡前心情值分別為 $11$ 與 $8$，內耗程度依然是 $3$。
第九天去飯店 $8$ 參加聚會，心情值變為 $8 + 1\times | 8-7 | + 15 = 22$。雖然內耗程度又增加為 $6$，但隔天不管有沒有窩著耍廢、內耗都不重要。
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~3 | 範例測資。 | 0 |
| 2 | 4~23 | $K=0$。 | 25 |
| 3 | 24~43 | $N,T \leq 5000$。 | 20 |
| 4 | 0~3, 24~67 | $N,T \leq 10^ 5$。 | 35 |
| 5 | 0~86 | 無特別限制。 | 20 |