oj.uz

Submission #946011

# Submission time Handle Problem Language Result Execution time Memory
946011 2024-03-14T09:33:38 Z siewjh Road Construction (JOI21_road_construction) C++17
6 / 100
 114 ms 13700 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 33 ms 2908 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 10432 KB Output is correct
2 Correct 114 ms 13424 KB Output is correct
3 Correct 35 ms 2900 KB Output is correct
4 Correct 100 ms 13572 KB Output is correct
5 Correct 81 ms 13700 KB Output is correct
6 Correct 86 ms 13436 KB Output is correct
7 Correct 85 ms 13516 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 64 ms 10444 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 64 ms 10444 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 33 ms 2908 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 33 ms 2908 KB Output isn't correct
2 Halted 0 ms 0 KB -