제한된 제거 - 题目

Alice와 Bob에게 길이가 $N$인 정수 배열 $A$가 주어집니다.

Alice는 1이 정확히 $K$개 포함된 길이가 $N$인 이진 문자열 $B$를 선택하며, 이 문자열은 게임이 끝날 때까지 고정됩니다.

어느 시점에서든 인덱스 $i$는 $B_i = 1$일 때만 보호되며, Bob은 $B_i = 0$일 때만 인덱스 $i$를 선택할 수 있습니다.

Bob은 0번 이상의 이동을 수행합니다. Bob의 초기 점수는 $0$입니다.

한 번의 이동에서 Bob은 다음 조건을 만족하는 인덱스 $i$를 선택합니다:

Bob은 현재 값 $A_i$를 자신의 점수에 더하고 이 원소를 $A$에서 제거합니다. 매 삭제 후 $|A|$는 $1$씩 감소하며, $A$의 남은 원소들은 $1$부터 $|A|$까지 다시 인덱스가 매겨집니다.

따라서 $B$는 고정된 원소 자체가 아니라 현재의 인덱스 위치에 적용됩니다. 원소들이 밀린 후에는 같은 원소가 보호되거나 제거 가능해질 수 있습니다.

Bob이 여러 번의 이동에 걸쳐 선택한 인덱스들을 $P_1, P_2, \dots, P_m$이라고 할 때, 이들은 비증가해야 합니다. 즉,

$$P_1 \ge P_2 \ge \dots \ge P_m$$

이어야 합니다. Bob은 같은 인덱스를 여러 번 선택할 수 있습니다.

Alice는 Bob의 점수를 최소화하려 하고, Bob은 자신의 점수를 최대화하려 합니다.

두 플레이어가 모두 최적으로 플레이했을 때 Bob의 최종 점수를 구하세요.

입력은 다음 형식으로 주어집니다:

T
N K
A1 A2 ... AN
...

각 테스트 케이스에 대해, Bob의 최종 점수를 나타내는 하나의 정수를 출력합니다.

6
5 2
4 -1 7 -3 2
4 0
-5 -2 -1 -3
4 4
2 -7 5 1
1 0
-1
2 1
0 1
3 1
1 -1 1

테스트 케이스 1: Alice는 $B = 10001$을 선택할 수 있습니다. 그러면 처음에 Bob이 사용할 수 있는 인덱스는 $2$, $3$, $4$이고 각각의 값은 $-1$, $7$, $-3$입니다. Bob은 인덱스 $3$을 한 번 선택하여(값 $7$을 더함) 점수 $7$을 보장받을 수 있습니다. 그 이후에 선택하는 모든 인덱스는 최대 $3$이어야 하므로 인덱스 $4$는 선택할 수 없으며, 이후의 어떤 올바른 이동도 양수가 아닌 값을 더하게 됩니다. Alice는 Bob이 $7$보다 더 큰 점수를 얻지 못하도록 강제할 수 있으므로 답은 $7$입니다.
테스트 케이스 2: $K = 0$이므로 Alice는 선택의 여지 없이 $B = 0000$을 선택해야 합니다. Bob은 모든 인덱스를 사용할 수 있지만 배열의 모든 값이 음수입니다. 어떤 이동을 하더라도 Bob의 점수가 감소하므로, Bob의 최적 플레이는 아무 이동도 하지 않는 것입니다. 따라서 답은 $0$입니다.
테스트 케이스 3: $K = N$이므로 Alice는 선택의 여지 없이 $B = 1111$을 선택해야 합니다. 모든 위치가 보호되어 있으므로 Bob은 할 수 있는 올바른 이동이 전혀 없습니다. 따라서 Bob의 점수는 $0$입니다.

QOJ.ac