Submission #1157722

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157722		adlin	Road Construction (JOI21_road_construction)	C++20	5 / 100	85 ms	9356 KiB

road_construction

#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define int long long 

using namespace std;

typedef long long ll;

const int maxn = 250001;

int n,k;

pair <int,int> a[maxn];

signed main(){
	
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	bool ok = 1;
	
	cin >> n >> k;
	
	for(int i = 1; i <= n; i++){
		cin >> a[i].F >> a[i].S;
		if(a[i].S) ok = 0;
	}
	
	if(n <= 1000){
		vector <ll> v;
		
		for(int i = 1; i <= n; i++){
			for(int j = i + 1; j <= n; j++){
				v.pb((ll)abs(a[i].F-a[j].F) + abs(a[i].S-a[j].S));
			}
		}
		
		sort(v.begin(),v.end());
		
		for(int i = 0; i < k; i++) cout << v[i] << '\n';
	}
	else if(ok){
		sort(a + 1, a + n + 1);
		
		vector <ll> v;
		
		ll cur = 0;
		
		for(int i = 1; i < n; i++){
			if(cur + n - i <= k){
				int l = 1, r = i + 1; 
				while(r <= n){
					v.pb((ll)abs(a[r].F - a[l].F));
					l++;
					r++;
				}
				cur += n - i;	
			}
			else {
				int l = 1, r = i + 1;
				vector <ll> v2;
				while(r <= n){
					v2.pb((ll)abs(a[r].F - a[l].F));
					l++;
					r++;
				}
				k -= cur;
				sort(v2.begin(),v2.end());
				for(int j = 0; j < k; j++) v.pb(v2[j]);
				break;
			}
		}
		
		sort(v.begin(),v.end());
		
		for(auto i : v) cout << i << '\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