#include<bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, K;
cin >> N >> K;
vector<int> T(N);
for (int i = 0; i < N; ++i) {
cin >> T[i];
}
sort(T.begin(), T.end());
vector<pair<int, int>> intervals;
int start = T[0];
int end = T[0] + 1;
for (int i = 1; i < N; ++i) {
if (T[i] == end) {
++end;
} else {
intervals.push_back({start, end});
start = T[i];
end = T[i] + 1;
}
}
intervals.push_back({start, end});
int m = intervals.size();
if (m <= K) {
int total = 0;
for (auto [s, e] : intervals) {
total += (e - s);
}
cout << total << endl;
return 0;
}
vector<int> gaps;
for (int i = 0; i < m - 1; ++i) {
int gap = intervals[i + 1].first - intervals[i].second;
gaps.push_back(gap);
}
sort(gaps.begin(), gaps.end());
int totalTime = 0;
for (auto [s, e] : intervals) {
totalTime += (e - s);
}
for (int i = 0; i < m - K; ++i) {
totalTime += gaps[i];
}
cout << totalTime << endl;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |