Submission #66774

#	Time	Username	Problem	Language	Result	Execution time	Memory
66774		quoriess	Stove (JOI18_stove)	C++14	100 / 100	279 ms	17788 KiB

stove

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
typedef pair<lli,lli> pii;
typedef pair<lli,pii> data;
int main(){
	int n,k;
	cin>>n>>k;
	vector<lli> times;
	map<lli,bool> marked;
	for (int i = 0; i < n; i++)
	{
		int a;
		cin>>a;
		if(marked.find(a)==marked.end()){
			times.push_back(a);
		}
		if(marked.find(a+1)==marked.end()){
			times.push_back(a+1);
		}
		marked[a+1]=true;
		marked[a]=false;
	}
	k--;
	sort(times.begin(),times.end());
	int len=times.size();
	priority_queue<lli> maxBosluklar;
	for (int i = 1; i < len; i++)
	{
		if(marked[times[i-1]]){
			maxBosluklar.push(times[i]-times[i-1]);
		}
	}
	lli sz=times[len-1]-times[0];
	while(k>0 && !maxBosluklar.empty()){
		lli t=maxBosluklar.top();
		maxBosluklar.pop();
		sz-=t;
		k--;
	}
	cout << sz<<"\n";
	return 0;
}

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