#include <bits/stdc++.h>
using namespace std;
#define int long long
int find(int x, vector<int>&par) { return x == par[x] ? x : find(par[x], par); }
bool same(int x, int y, vector<int>&par) { return find(x, par) == find(y, par); }
void unite(int x, int y, vector<int>&sz, vector<int>&par) {
x = find(x, par), y = find(y, par);
if (sz[x] < sz[y]) swap(x, y);
sz[x] += sz[y], par[y] = x;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
vector<int> arr(n + 5);
for (int i = 1; i <= n; i++) cin >> arr[i];
vector<int> sz(n + 5), par(n + 5), mn(n + 5), mx(n + 5);
for (int i = 1; i <= n; i++) par[i] = i, sz[i] = 1, mn[i] = mx[i] = arr[i];
vector<pair<int, int>> edge;
for (int i = 2; i <= n; i++) edge.push_back({arr[i] - arr[i - 1], i});
sort(edge.begin(), edge.end());
int cc = n;
for (int i = 0; i < edge.size() && cc > k; i++) {
int index = edge[i].first;
if (!same(index, index - 1, par)) unite(index, index - 1, sz, par), cc--;
}
for (int i = 1; i <= n; i++) {
mn[find(i, par)] = min(mn[find(i, par)], arr[i]);
mx[find(i, par)] = max(mx[find(i, par)], arr[i]);
}
int ans = 0;
for (int i = 1; i <= n; i++) {
if (find(i, par) == i) {
ans += mx[i] - mn[i] + 1;
}
}
cout << ans << '\n';
return 0;
}
Compilation message
stove.cpp: In function 'int main()':
stove.cpp:31:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
31 | for (int i = 0; i < edge.size() && cc > k; i++) {
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
