c180: B.飲料
標籤 :
通過比率 : 83% (10 人 / 12 人 ) (非即時)
評分方式:
Tolerant

最近更新 : 2017-04-10 20:47

內容 :

  買完門票後,小Y一行人進入了延平遊樂園。一進去樂園,馬上看到一家賣飲料的飲料店(飲料店就是要來賣飲料的啊XD)。

 

  這家飲料店總共有賣N種飲料,飲料編號為1,2,3, ……, N-1, N,每種飲料都有各自的可口度ai,可口度可以是正數,代表著這杯飲料可以帶來實質上的美味,可口度是負數,帶表喝下這杯飲料後,身體可能會產生不良反應等。可口度也可以是0,代表你喝下飲料後,沒有實質上的感覺。當你喝了多杯飲料,總共的可口度就是那些飲料的可口度總和。

 

  特別地,在這些飲料中,有M組飲料配對。每組配對可以表示為(bi, ci, di),代表如果一個人同時喝下了bici這兩種飲料,會感受到額外的可口度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,代表如果一個人同時喝下了bici這兩種飲料,會感受到額外的可口度di (1≤bi<ciN,|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
測資資訊:
記憶體限制: 256 MB
公開 測資點#0 (3%): 1.0s , <1K
公開 測資點#1 (3%): 1.0s , <1K
公開 測資點#2 (3%): 1.0s , <1K
公開 測資點#3 (3%): 1.0s , <1K
公開 測資點#4 (3%): 1.0s , <1K
公開 測資點#5 (3%): 1.0s , <1K
公開 測資點#6 (3%): 1.0s , <1K
公開 測資點#7 (3%): 1.0s , <1K
公開 測資點#8 (3%): 1.0s , <1M
公開 測資點#9 (3%): 1.0s , <1M
公開 測資點#10 (3%): 1.0s , <1M
公開 測資點#11 (3%): 1.0s , <1M
公開 測資點#12 (3%): 1.0s , <1M
公開 測資點#13 (3%): 5.0s , <10M
公開 測資點#14 (3%): 5.0s , <10M
公開 測資點#15 (3%): 5.0s , <10M
公開 測資點#16 (3%): 5.0s , <10M
公開 測資點#17 (3%): 5.0s , <10M
公開 測資點#18 (3%): 5.0s , <10M
公開 測資點#19 (3%): 5.0s , <10M
公開 測資點#20 (3%): 5.0s , <10M
公開 測資點#21 (3%): 5.0s , <10M
公開 測資點#22 (3%): 5.0s , <10M
公開 測資點#23 (3%): 5.0s , <10M
公開 測資點#24 (3%): 5.0s , <10M
公開 測資點#25 (3%): 5.0s , <10M
公開 測資點#26 (3%): 5.0s , <10M
公開 測資點#27 (3%): 5.0s , <10M
公開 測資點#28 (3%): 5.0s , <10M
公開 測資點#29 (3%): 5.0s , <10M
公開 測資點#30 (3%): 5.0s , <10M
公開 測資點#31 (3%): 5.0s , <10M
公開 測資點#32 (4%): 5.0s , <10M
提示 :

編號

配分

測資範圍

1~3

9%

1≤N≤100, M=0, 1≤i≤10

4~8

15%

1≤N≤100, M=0, |i|≤1000

9~13

15%

1≤N≤3000, M=0, |a­i|≤10000

14~23

30%

1≤N≤300000, M=0, |a­i|≤109

24~33

31%

1≤N≤3*105, 0≤M≤3*10­5, |ai|,|di|≤109, 1≤bi<ciN

 

題目敘述更新,增加subtask限制。(2017/04/30 20:47)

 

標籤:
出處:
2016下學期延平中學高中組校內程式設計競賽 [編輯: fishtoby (瓜瓜) ]
編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」