Submission #1294901

#	Time	Username	Problem	Language	Result	Execution time	Memory
1294901		kian2009	Road Construction (JOI21_road_construction)	C++20	5 / 100	10086 ms	7172 KiB

road_construction

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

typedef long long ll;

const int MAXN = 3e5 + 10;

ll n, k, x[MAXN], y[MAXN];
priority_queue<ll> q;

void input() {
	cin >> n >> k;
	for (int i = 0; i < n; i++)
		cin >> x[i] >> y[i];	
}

void findAns() {
	for (int i = 0; i < n; i++)
		for (int j = i + 1; j < n; j++) {
			ll h = abs(x[j] - x[i]) + abs(y[j] - y[i]);
			if (q.size() < k || q.top() > h) {
				if (q.size() < k)
					q.push(h);
				else {
					q.pop();
					q.push(h);	
				}
			}
		}
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0);
	input();
	findAns();
	vector<ll> res;
	while (!q.empty()) {
		res.push_back(q.top());
		q.pop();	
	}
	reverse(res.begin(), res.end());
	for (auto x : res)
		cout << x << '\n';
	return 0;	
}

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