2177 . 這是抄襲的問題

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
Waimai∼

User's AC Ratio

94.1% (32/34)

Submission's AC Ratio

44.7% (63/141)

Tags

CKsim 2020-CKsim

Description

今天ZCK想要出練習賽，但是他不想要抄襲別人的題目
所以雖然他每天都會看到各種毒又毒的題目，他並不會隨便拿來毒別人
他想辦法生出了一些題目，這些題目分別有一些(大家評估的)優質度還有難度(難度都相異)
不過，有些題目是自己想到的，有些題目是從別的OJ抓來的(會告訴你每個題目是自己想到的還是從某個編號的OJ抓的)
因為是練習賽，他希望題目可以照難度排序
他希望選一組題目，難度遞增並且總優質度越高越好
但是，他不太希望參賽者看到題目都從同一個OJ上抄來，不然很容易被抓包然後罵翻
ZCK所看到的題目總共有N個，然後這些題目都是從M個OJ裡頭抓出來的或者是自己出的。
因此ZCK將選出，假設選出了K個題目P1,P2,…,PK，那麼對於1≤i<K，如果Pi,Pi+1的來源是同一個OJ的話，總優質度就得扣掉一次該OJ的知名度
以上的條件有一個特例，也就是如果題目是ZCK自己出的話，那就不必扣掉知名度（因為ZCK是無限知名的）
（就算是同一個OJ，在很多位置出現的話當然得扣掉那麼多次）
也就是說，一組題目的總優質度是「所有題目的優質度的總和」扣掉「所有相鄰的題目且來源是同一個OJ的OJ知名度」

Input Format

第一行有一個正整數N,M表示總共有N道題目，還有M種OJ
第二行有M個用空白隔開的非負整數，第i個數字Ai表示第i種OJ的知名度
接下來N行，每行有三個數字Q,D,X，分別代表該題的優質度、難度跟是從什麼編號的OJ抓的。如果X=0代表那是ZCK自己產出的題目，不用擔心跟相鄰的題目撞OJ
有些題目實在太毒了，或是水到不是題目，因此有些題目的優質度可能小於零
N,M≤5000
0≤Ai≤109
−109≤Q≤109
0≤D≤10000
0≤X≤M

Output Format

請輸出一行整數表示最佳的總優質度
注意你可以不選任何題目，所以答案不會是負的

Sample Input 1

3 1
7122
3 1 0
4 2 0
5 3 0

Sample Output 1

12

Sample Input 2

5 1
700
900 1800 1
600 2700 1
800 2100 1
700 2400 1
600 3500 1

Sample Output 2

1000

Sample Input 3

7 8
5 7 5 9 5 1 4 3
10 1300 0
10 600 1
4 1100 0
2 2300 1
10 2000 1
0 1700 8
9 1800 7

Sample Output 3

43

Hints

JOJO，這是我最後的波紋了！

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~4 N≤10，難度分別依序是1,2,⋯,N，並且所有X都是0 10
2 0~14 N≤10 20
3 0~29 無其他限制 70

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2 3
1 1000 524288 65536 1 2 3
2 1000 524288 65536 1 2 3
3 1000 524288 65536 1 2 3
4 1000 524288 65536 1 2 3
5 1000 524288 65536 2 3
6 1000 524288 65536 2 3
7 1000 524288 65536 2 3
8 1000 524288 65536 2 3
9 1000 524288 65536 2 3
10 1000 524288 65536 2 3
11 1000 524288 65536 2 3
12 1000 524288 65536 2 3
13 1000 524288 65536 2 3
14 1000 524288 65536 2 3
15 1000 524288 65536 3
16 1000 524288 65536 3
17 1000 524288 65536 3
18 1000 524288 65536 3
19 1000 524288 65536 3
20 1000 524288 65536 3
21 1000 524288 65536 3
22 1000 524288 65536 3
23 1000 524288 65536 3
24 1000 524288 65536 3
25 1000 524288 65536 3
26 1000 524288 65536 3
27 1000 524288 65536 3
28 1000 524288 65536 3
29 1000 524288 65536 3
Submit
Back to Top