Submission #208553

#	Time	Username	Problem	Language	Result	Execution time	Memory
208553		teomrn	Stove (JOI18_stove)	C++14	100 / 100	128 ms	7920 KiB

stove

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

class Heap {
	struct HeapNode {
		int val;
		vector <HeapNode*> fii;
		HeapNode(int val) : val(val) { }
	} *root;

	HeapNode* join(HeapNode* a, HeapNode* b) {
		if (a == 0)
			return b;
		if (b == 0)
			return a;
		if (a->val < b->val) {
			a->fii.push_back(b);
			return a;
		}
		// else
		b->fii.push_back(a);
		return b;
	}

public:
	Heap() : root(0) { }

	void push(int val) {
		HeapNode* nod = new HeapNode(val);
		root = join(root, nod);
	}

	int top() {
		assert(root != 0);
		return root->val;
	}

	void pop() {
		HeapNode* new_root = 0;
		if (root->fii.size() % 2 == 1)
			root->fii.push_back(0);
		for (int i = 0; i < (int)root->fii.size(); i += 2)
			new_root = join(new_root,
				join(root->fii[i], root->fii[i + 1]));
		delete root;
		root = new_root;
	}
};

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);
	Heap 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