| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 1024 MB | 17 | 8 | 5 | 55.556% |
특별 훈련 기간을 맞아, 총 $N$개의 부대가 서로 협동하는 합동 훈련이 진행된다. 합동 훈련을 한 번 진행할 때마다 총 2ドルN$명의 병사를 선발하는데, 각 부대에서 선발할 수 있는 병사의 수에는 제한이 없으며 병사가 한 명도 참여하지 않는 미참여 부대도 있을 수 있다. 훈련에 참여하는 부대에서는 병사들을 훈련지로 수송하기 위해 버스를 대절하는데, 각 부대에서 버스를 대절하는 비용은 각각 $a_i$이다. 합동 훈련의 비용은, 훈련에 참여하는 부대의 버스 대절 비용의 합이다.
합동 훈련은 2ドルN$명의 병사들이 일렬로 서서 진행된다. 훈련이 끝난 뒤, 인접하게 서 있던 모든 병사 쌍마다 소속 부대 간 불만도가 1ドル$씩 증가한다. 단, 동일한 부대끼리는 서로 인접하게 서 있었더라도 불만도가 증가하지 않는다. 인접한 병사들의 소속 부대 간 불만도가 너무 높으면 훈련이 제대로 진행되지 않을 것을 우려한 지휘관은 서로 불만도가 $K$ 이상인 부대의 병사들끼리 인접하게 서는 훈련 계획은 승인하지 않는다. 단, 훈련이 진행되기 전에는 각 부대의 불만도는 서로 0ドル$이다.
특별 훈련 기간 동안, 지휘관은 다음의 세 가지 사건에 대한 보고서를 작성하여야 한다.
이때, 각 사건으로 인한 불만도 증가 및 비용 증가는 모든 사건이 끝나기 전까지 누적되어 유지된다.
그러나 안 그래도 바쁜 지휘관은 위 세 가지 사건에 대한 보고서를 작성할 시간이 없었고, 당신에게 위 세 가지 사건에 대한 보고서를 대신 작성해 달라는 부탁과 함께 사라져 버렸다! 지휘관을 위해 각 사건에 대한 보고서를 작성해 주자.
첫 번째 줄에 부대의 개수 $N$과 서로 인접하지 못하는 최소 불만도 $K$가 공백으로 구분되어 정수로 주어진다.
두 번째 줄에 각 부대의 버스 대절 비용 $a_i$가 공백으로 구분되어 정수로 주어진다.
세 번째 줄에 사건이 일어난 횟수 $Q$가 주어진다.
이후 $Q$줄에 걸쳐 사건의 종류 $q_i$와 각 사건에 대한 변수가 다음과 같이 주어진다.
$i$번째 줄에, $i$번째 사건에 대한 답변을 다음과 같이 출력한다.
-1을 출력한다.| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 35 | $N\leq 5,000円;$ $q_i=1$ |
| 2 | 105 | $N\leq 5,000円;$ $q_i\leq 2$ |
| 3 | 80 | $N\leq 5,000円$ |
| 4 | 95 | $q_i\leq 2$ |
| 5 | 85 | 추가 제한 없음 |
3 4 1 2 4 5 1 2 1 1 3 3 1 1 3 3 3 3 3 3 2 1 3 8 2 3 2 5 3 1 1
7 4 7 4 1
첫 번째 사건에서는, 각 부대의 불만도가 모두 0ドル$이므로 훈련을 진행한다. 훈련이 진행된 후, 부대 1ドル$과 부대 2ドル$는 서로 불만도 1ドル$을, 부대 1ドル$과 부대 3ドル$은 서로 불만도 2ドル$를 가지게 되었으며, 세 부대가 모두 참여하였으므로 1ドル+2+4=7$의 비용이 든다.
두 번째 사건에서는, 부대 3ドル$만 참여하였으므로 각 부대간의 불만도는 변하지 않았으며, 총 4ドル$의 비용이 들었다.
세 번째 사건에서는, 부대 1ドル$과 3ドル$의 불만도가 8ドル$만큼 증가하여 총 불만도가 10ドル$이 되었다. 따라서, 이후의 훈련에서는 부대 1ドル$과 부대 3ドル$은 인접하게 설 수 없다. 만약 병사들을 일렬로 순서대로 $\{3, 3, 2, 2, 1, 1\}$ 으로 훈련을 진행하면 인접한 병사의 불만도는 모두 4ドル$ 미만이며, 이 때의 비용은 총 7ドル$이 든다.
네 번째 사건에서는, 부대 2ドル$와 3ドル$의 불만도가 5ドル$만큼 증가하였으므로, 이후의 훈련에서는 두 부대의 병사가 서로 인접하게 설 수 없다.
이 경우, 최대 비용을 가지는 훈련 계획은 3ドル$번 부대의 병사만 2ドルN$명 선발하는 경우 하나 뿐이며, 이 경우 비용은 총 4ドル$가 든다.
다섯 번째 사건에서는, 부대 1ドル$의 버스 대절 비용이 1ドル$만큼 증가하여 비용이 2ドル$가 되었다. 부대 1ドル$을 포함하는 가능한 훈련 계획으로는 $\{1, 1, 2, 2, 1, 2\}$ 등 부대 1ドル$과 부대 2ドル$만으로 훈련 계획을 구성하는 경우 뿐이며, 이 경우 두 부대의 비용이 모두 2ドル$이므로 서로 다른 비용의 개수는 하나 뿐이다.
Contest > 보라매컵 > 제2회 보라매컵 예선 F번