#include<bits/stdc++.h>
#define f first
#define s second
using namespace std;
const int N = 2e5 + 500;
typedef pair<int , int> ipair;
int n , k;
int a[N];
vector<ipair> deltas;
set<int> s;
int main (){
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n >> k;
for(int i = 0; i < n; ++i){
cin >> a[i];
if(i) deltas.emplace_back(a[i] - a[i - 1] , i - 1);
}
sort(deltas.begin() , deltas.end()); reverse(deltas.begin() , deltas.end());
for(int i = 0; i < k - 1; ++i){
s.insert(deltas[i].s);
//cerr << deltas[i].s << " ";
} //cerr << endl;
long long sum = 0;
int cur = 0;
for(int x : s){
//cerr << x << " x " << "cur " << cur << endl;
sum += (a[x] + 1 - a[cur]);
//cerr << a[x] << " a[x] " << " acur " << a[cur] << endl;
//cerr << sum << " sum " << endl;
cur = x + 1;
} sum += (a[n - 1] + 1 - a[cur]);
cout << sum << endl;
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
4 ms |
256 KB |
Output is correct |
| 3 |
Correct |
5 ms |
384 KB |
Output is correct |
| 4 |
Correct |
4 ms |
384 KB |
Output is correct |
| 5 |
Correct |
5 ms |
384 KB |
Output is correct |
| 6 |
Correct |
4 ms |
384 KB |
Output is correct |
| 7 |
Correct |
5 ms |
384 KB |
Output is correct |
| 8 |
Correct |
5 ms |
384 KB |
Output is correct |
| 9 |
Correct |
5 ms |
384 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
4 ms |
256 KB |
Output is correct |
| 3 |
Correct |
5 ms |
384 KB |
Output is correct |
| 4 |
Correct |
4 ms |
384 KB |
Output is correct |
| 5 |
Correct |
5 ms |
384 KB |
Output is correct |
| 6 |
Correct |
4 ms |
384 KB |
Output is correct |
| 7 |
Correct |
5 ms |
384 KB |
Output is correct |
| 8 |
Correct |
5 ms |
384 KB |
Output is correct |
| 9 |
Correct |
5 ms |
384 KB |
Output is correct |
| 10 |
Correct |
5 ms |
384 KB |
Output is correct |
| 11 |
Correct |
5 ms |
512 KB |
Output is correct |
| 12 |
Correct |
6 ms |
512 KB |
Output is correct |
| 13 |
Correct |
6 ms |
512 KB |
Output is correct |
| 14 |
Correct |
6 ms |
512 KB |
Output is correct |
| 15 |
Correct |
6 ms |
512 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
4 ms |
256 KB |
Output is correct |
| 3 |
Correct |
5 ms |
384 KB |
Output is correct |
| 4 |
Correct |
4 ms |
384 KB |
Output is correct |
| 5 |
Correct |
5 ms |
384 KB |
Output is correct |
| 6 |
Correct |
4 ms |
384 KB |
Output is correct |
| 7 |
Correct |
5 ms |
384 KB |
Output is correct |
| 8 |
Correct |
5 ms |
384 KB |
Output is correct |
| 9 |
Correct |
5 ms |
384 KB |
Output is correct |
| 10 |
Correct |
5 ms |
384 KB |
Output is correct |
| 11 |
Correct |
5 ms |
512 KB |
Output is correct |
| 12 |
Correct |
6 ms |
512 KB |
Output is correct |
| 13 |
Correct |
6 ms |
512 KB |
Output is correct |
| 14 |
Correct |
6 ms |
512 KB |
Output is correct |
| 15 |
Correct |
6 ms |
512 KB |
Output is correct |
| 16 |
Correct |
30 ms |
2684 KB |
Output is correct |
| 17 |
Correct |
29 ms |
2684 KB |
Output is correct |
| 18 |
Correct |
29 ms |
2684 KB |
Output is correct |
| 19 |
Correct |
35 ms |
3080 KB |
Output is correct |
| 20 |
Correct |
45 ms |
4848 KB |
Output is correct |
| 21 |
Correct |
60 ms |
6768 KB |
Output is correct |
| 22 |
Correct |
66 ms |
7156 KB |
Output is correct |
| 23 |
Correct |
64 ms |
7148 KB |
Output is correct |
| 24 |
Correct |
64 ms |
7152 KB |
Output is correct |
