Submission #208552

#	Time	Username	Problem	Language	Result	Execution time	Memory
208552		teomrn	Stove (JOI18_stove)	C++14	100 / 100	37 ms	2424 KiB

stove

#include <bits/stdc++.h>
using namespace std;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int n, k;
	cin >> n >> k;

	vector <int> v(n);
	for (auto& i : v)
		cin >> i;

	sort(v.begin(), v.end());

	int interv_need = max(0, (int)v.size() - k);
	priority_queue <int> pq;

	for (int i = 1; i < (int)v.size(); i++)
		pq.push(-(v[i] - v[i - 1] - 1));

	int ans = v.size();
	for (int _ = 0; _ < interv_need; _++) {
		ans -= pq.top();
		pq.pop();
	}

	cout << ans << '\n';

	return 0;
}

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