Submission #946011

#	Time	Username	Problem	Language	Result	Execution time	Memory
946011		siewjh	Road Construction (JOI21_road_construction)	C++17	6 / 100	114 ms	13700 KiB

road_construction

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int nums, k; cin >> nums >> k;
	vector<ll> xv(nums), yv(nums);
	for (int i = 0; i < nums; i++) cin >> xv[i] >> yv[i];
	sort(xv.begin(), xv.end());
	vector<int> ind(nums);
	for (int i = 0; i < nums; i++) ind[i] = i - 1;
	priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
	for (int i = 1; i < nums; i++) pq.push({xv[i] - xv[i - 1], i});
	for (int i = 0; i < k; i++){
		ll v; int id; tie(v, id) = pq.top(); pq.pop();
		cout << v << '\n';
		ind[id]--;
		if (ind[id] != -1) pq.push({xv[id] - xv[ind[id]], id});
	}
}

• Subtask 1: 0 / 5
• Subtask 2: 6 / 6
• Subtask 3: 0 / 7
• Subtask 4: 0 / 20
• Subtask 5: 0 / 27
• Subtask 6: 0 / 35