This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define boost ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long
using namespace std;
const int N = 1e5 + 4;
const int inf = 1e18;
struct edge {
int a,b,c,d;
};
vector<int>v;
vector<pair<int,int> >v1;
vector<int>v2;
signed main(){
//freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
boost;
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++){
int x;
cin>>x;
v.push_back(x);
}
for(int i=0;i<n-1;i++){
v1.push_back({v[i+1]-v[i]-1,i});
}
sort(v1.rbegin(),v1.rend());
for(int i=0;i<k-1;i++){
v2.push_back(v1[i].second);
}
sort(v2.begin(),v2.end());
int j=0;
int st=0;
int ans=0;
if(v2.size()==1){
cout<<v[n-1]-v[0]+1;
return 0;
}
for(int i=0;i<v.size();i++){
if(j<v2.size()&&i==v2[j]){
j++;
ans+=v[i]+1-v[st];
st=i+1;
}
}
ans+=v[n-1]-v[st]+1;
cout<<ans;
}
Compilation message (stderr)
stove.cpp: In function 'int main()':
stove.cpp:40:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
40 | for(int i=0;i<v.size();i++){
| ~^~~~~~~~~
stove.cpp:41:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
41 | if(j<v2.size()&&i==v2[j]){
| ~^~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |