Submission #671008

#	Time	Username	Problem	Language	Result	Execution time	Memory
671008		Arixcrest	Stove (JOI18_stove)	C++17	100 / 100	19 ms	2264 KiB

stove

#include <bits/stdc++.h>
using namespace std;
 
using ll =  long long;
#define pi pair<int,int> 
#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define getunique(v) {sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end());}
const ll INF = -1;
const int mx = 1e5+5;
const int modulo =1e9+7;
mt19937 mt;
void solve(){
	int n,k;
	cin>>n>>k;
	vector<int> arr(n);
	rep(x,0,n) cin>>arr[x];
	vector<int> distances;
	ll ans = n;
	rep(x,1,n){
		distances.push_back(arr[x]-arr[x-1]-1);
	}
	sort(distances.begin(),distances.end(),greater<int>());
	while(n>k){
		// cout<<n<<" "<<k<<'\n';
		ans+=distances.back();
		distances.pop_back();
		n--;
	}
	cout<<ans<<"\n";

}
 
 
 
 
 
 
 
 
int main(){
	ios_base ::sync_with_stdio(0), cin.tie(0);
	clock_t start, end;
	start = clock();
	int t = 1;
	// cin >> t;
	// int x=0;
	while (t-->0)
	{
        //cout<<"Case #"<<x<<": ";
		solve();
        // x++;
	}
	end = clock();
	cerr << double(end - start) / double(CLOCKS_PER_SEC) << '\n';
}

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 50 / 50