Submission #860219

#TimeUsernameProblemLanguageResultExecution timeMemory
860219StefanSebezStove (JOI18_stove)C++14
100 / 100
70 ms6552 KiB
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
int main()
{
    int n,k;cin>>n>>k;
    int a[n+1];
    set<pair<int,int> >st;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	int res=0;
	for(int i=1;i<n;i++)
	{
		st.insert({a[i+1]-a[i],i});
	}
	/*auto i=st.begin();
	while(i!=st.end())
	{
		pair<int,int> x=*i;
		cout<<x.fi<<" "<<x.se<<endl;
		i=next(i);
	}*/
	//res=a[n]-a[1]+1;
	bool was[n+1]={0};
	int ct=1;
	while(ct<k && !st.empty())
	{
		pair<int,int>x=*st.rbegin();
		//res-=x.fi;
		ct++;
		was[x.se]=true;
		st.erase(x);
		//cout<<res<<endl;
	}
	for(int i=1;i<n;i++)
	{
		if(!was[i])res+=a[i+1]-a[i];
	}
	res+=ct;
	cout<<res<<endl;
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...