Submission #577884

#	Time	Username	Problem	Language	Result	Execution time	Memory
577884		haxorman	Stove (JOI18_stove)	C++14	100 / 100	35 ms	6080 KiB

stove

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

#define int long long

const int mxN = 1e5 + 7;

int n, k, arr[mxN], dsu[mxN];

int find(int x) {
	return (dsu[x] < 0 ? x : dsu[x] = find(dsu[x]));
}

bool unite(int x, int y) {
	x = find(x), y = find(y);

	if (x == y) {
		return false;
	}

	if (dsu[x] > dsu[y]) {
		swap(x, y);
	}

	dsu[x] += dsu[y];
	dsu[y] = x;

	return true;
}

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

	cin >> n >> k;
	memset(dsu, -1, sizeof(dsu));

	for (int i = 0; i < n; ++i) {
		cin >> arr[i];
	}
	sort(arr, arr + n);
	
	vector<pair<int,pair<int,int>>> difs;
	for (int i = 0; i < n - 1; ++i) {
		difs.push_back({arr[i + 1] - arr[i], {i + 1, i}});
	}
	sort(difs.begin(), difs.end());
	
	int ans = n, cnt = n;
	for (auto p : difs) {
		int dif = p.first, u = p.second.first, v = p.second.second;

		if (unite(u, v) && cnt > k) {
			//cout << dif << ' ' << u << ' ' << v << "\n";
			ans += dif - 1;
			--cnt;
		}
	}

	cout << ans << "\n";
}

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