買完門票後，小Y一行人進入了延平遊樂園。一進去樂園，馬上看到一家賣飲料的飲料店(飲料店就是要來賣飲料的啊XD)。
這家飲料店總共有賣N種飲料，飲料編號為1,2,3, ……, N-1, N，每種飲料都有各自的可口度ai，可口度可以是正數，代表著這杯飲料可以帶來實質上的美味，可口度是負數，帶表喝下這杯飲料後，身體可能會產生不良反應等。可口度也可以是0，代表你喝下飲料後，沒有實質上的感覺。當你喝了多杯飲料，總共的可口度就是那些飲料的可口度總和。
特別地，在這些飲料中，有M組飲料配對。每組配對可以表示為(bi, ci, di)，代表如果一個人同時喝下了bi與ci這兩種飲料，會感受到額外的可口度di。拿現實生活舉例的話，苦瓜水配茄子水的組合可口度就有可能是負數、可樂配汽水的組合就有可能是正數之類的，抑或是芭柳汁配泡沫綠茶的可口度也有可能是正的。我們保證這M組配對中不會有重複的配對出現。
現在，小Y希望選定兩個正整數L, R，並一口氣喝下編號第L, L+1, L+2 …… , R-1, R的這些飲料。注意，小Y至少要買一杯飲料，所以即便所有飲料的可口度都是負的，他也必須忍痛喝下一些。小Y想問，若L, R可以任選，他最高可以有多少滿足度？
第一行有兩個整數N , M(1≤N≤3*105, 0≤M≤3*105)，分別代表飲料的個數與配對的個數。
接下來的一行有N個整數a1, a2, ……, aN(|ai|≤109)，代表喝下每杯飲料所能獲得的可口度。
接下來有M行，每行有三個整數bi , ci , di，代表如果一個人同時喝下了bi與ci這兩種飲料，會感受到額外的可口度di (1≤bi<ci≤N,|di|≤109)。
輸出一個整數於一行，代表小Y可以獲得的最大總可口度。
7 7 6 2 -9 -4 3 1 0 1 6 8 1 4 -9 2 3 5 4 7 7 6 7 -1 2 5 7 2 6 3
19
|
編號 |
配分 |
測資範圍 |
|
1~3 |
9% |
1≤N≤100, M=0, 1≤ai≤10 |
|
4~8 |
15% |
1≤N≤100, M=0, |ai|≤1000 |
|
9~13 |
15% |
1≤N≤3000, M=0, |ai|≤10000 |
|
14~23 |
30% |
1≤N≤300000, M=0, |ai|≤109 |
|
24~33 |
31% |
1≤N≤3*105, 0≤M≤3*105, |ai|,|di|≤109, 1≤bi<ci≤N |
題目敘述更新，增加subtask限制。(2017/04/30 20:47)
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||