/ 
Time Limit: 5 sec / Memory Limit: 1024 MB
配点 : 525 点
問題文
N 個のボールが左右一列に並んでいます。
左から i (1\leq i\leq N) 番目のボールは色 C_i で、価値は V_i です。
高橋君はこの列から ちょうど K 個のボールを取り除いたうえで、 残ったボールを元の順番で並べたときに同じ色のボールが隣り合わないようにしたいと考えています。 また、その条件のもとで、列に残ったボールの価値の総和をなるべく大きくしたいと考えています。
高橋君が、残ったボールの列において同じ色のボールが隣り合わないように K 個のボールを取り除くことができるか判定し、 できる場合は列に残ったボールの価値の総和としてあり得る最大の値を求めてください。
制約
- 1\leq K<N\leq 2\times 10^5
- K\leq 500
- 1\leq C_i\leq N
- 1\leq V_i\leq 10^9
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N K C_1 V_1 C_2 V_2 \vdots C_N V_N
出力
高橋君が同じ色のボールが隣り合わないようにK 個のボールを取り除くことができる場合は、 列に残ったボールの価値の総和としてあり得る最大値を整数で出力せよ。 できない場合は、-1 を出力せよ。
入力例 1
5 2 1 1 3 5 3 3 1 4 1 2
出力例 1
10
左から、3,5 番目のボールを取り除くと、残ったボールは左から順に色 1,3,1 であるため、
どの隣り合う 2 つのボールの色も異なり、条件をみたしています。
このとき、列に残ったボールの価値の和は V_1+V_2+V_4=1+5+4=10 です。
他にも 5 つのボールから 2 つのボールを取り除く方法であって、同じ色のボールが隣り合わないようにできるものは存在しますが、
3,5 番目のボールを取り除いた時に残ったボールの価値の和は最大となります。
よって、10 を出力します。
入力例 2
3 1 1 10 1 10 1 10
出力例 2
-1
どのようにボールを 1 つ取り除いても色 1 のボールが隣り合ってしまいます。
よって、 -1 を出力します。
入力例 3
3 1 1 1 2 2 3 3
出力例 3
5
必ずちょうど K 個のボールを取り除く必要があることに注意してください。
Score: 525 points
Problem Statement
There are N balls lined up in a row.
The i-th ball from the left is of color C_i and has a value of V_i.
Takahashi wants to remove exactly K balls from this row so that no two adjacent balls have the same color when arranging the remaining balls without changing the order. Additionally, under that condition, he wants to maximize the total value of the balls remaining in the row.
Determine if Takahashi can remove K balls so that no two adjacent balls in the remaining row have the same color. If it is possible, find the maximum possible total value of the remaining balls.
Constraints
- 1\leq K<N\leq 2\times 10^5
- K\leq 500
- 1\leq C_i\leq N
- 1\leq V_i\leq 10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N K C_1 V_1 C_2 V_2 \vdots C_N V_N
Output
If Takahashi can remove K balls so that no two adjacent balls in the remaining row have the same color, print the maximum possible total value of the remaining balls as an integer. Otherwise, print -1.
Sample Input 1
5 2 1 1 3 5 3 3 1 4 1 2
Sample Output 1
10
After removing the 3-rd and 5-th balls from the left, the remaining balls are of colors 1, 3, 1 from left to right, so no two adjacent balls have the same color, satisfying the condition.
The total value of the remaining balls is V_1+V_2+V_4=1+5+4=10.
There are other ways to remove two balls from the five balls so that no two adjacent balls have the same color, but the total value of the remaining balls is maximized when removing the 3-rd and 5-th balls.
Hence, print 10.
Sample Input 2
3 1 1 10 1 10 1 10
Sample Output 2
-1
No matter how you remove one ball, balls of color 1 will end up next to each other.
Hence, print -1.
Sample Input 3
3 1 1 1 2 2 3 3
Sample Output 3
5
Note that exactly K balls must be removed.