#include<bits/stdc++.h>
using pair = std::array<int, 2>;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int N, k;
std::cin >> N >> k;
std::vector<int> V(N);
for (int i = 0; i < N; i++) {
std::cin >> V[i];
}
std::vector<pair> v;
for (int i = 0; i < N; i++) {
int j = i + 1;
while (j < N && V[j] == V[j - 1] + 1) j++;
v.push_back({V[i] - (V[0] - 1), j - i});
i = j - 1;
}
int n = v.size();
std::vector<int> parent(n), child(n);
std::vector<std::array<int, 3>> neigh(n); // 0 head 1 body 2 tail
std::set<pair> S;
for (int i = 0; i < n - 1; i++) {
neigh[i][0] = v[i][1];
neigh[i][2] = v[i +1][1];
neigh[i][1] = v[i + 1][0] - v[i][0] - v[i][1];
parent[i] = i - 1;
child[i] = i + 1;
S.insert({neigh[i][0] + neigh[i][1] + neigh[i][2], i});
}
int t = n-1;
while (t > k - 1) {
pair min = *S.begin(); S.erase(min);
int i = min[1];
auto par = neigh[parent[i]], chil = neigh[child[i]];
if (parent[i] >= 0) {
S.erase({par[0]+par[1]+par[2], parent[i]});
neigh[parent[i]][2] = min[0];
child[parent[i]] = child[i];
auto x = neigh[parent[i]];
S.insert({x[0] + x[1] + x[2], parent[i]});
}
if (child[i] < n) {
S.erase({chil[0]+chil[1]+chil[2], child[i]});
neigh[child[i]][0] = min[0];
parent[child[i]] = parent[i];
auto x = neigh[child[i]];
S.insert({x[0] + x[1] + x[2], child[i]});
}
t--;
}
if (n == 1) {
std::cout << v[0][1] << '\n';
return 0;
}
std::set<int> T;
for (auto u : S) {
T.insert(u[1]);
}
int ans = 0;
for (auto u : T) {
ans += neigh[u][0];
} ans += neigh[*(T.rbegin())][2];
std::cout << ans << '\n';
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
