Submission #381751

#	Time	Username	Problem	Language	Result	Execution time	Memory
381751		wind_reaper	Palembang Bridges (APIO15_bridge)	C++17	0 / 100	2 ms	492 KiB

bridge

#include <bits/stdc++.h>

using namespace std;

int64_t L, R;
priority_queue<int, vector<int>, greater<int>> rpq;
priority_queue<int> lpq;
const int INF = 1e9 + 1;

void insert(int x){
	int med = (lpq.size() ? lpq.top() : INF);

	if(x <= med){
		lpq.push(x);
		L += int64_t(x);
	}
	else{
		rpq.push(x);
		R += int64_t(x);
	}

	if(rpq.size() + 1 < lpq.size()){
		int nxt = lpq.top();
		lpq.pop();
		rpq.push(nxt);
		L -= int64_t(nxt);
		R += int64_t(nxt);
	}
	else if(lpq.size() < rpq.size()){
		int nxt = rpq.top();
		rpq.pop();
		lpq.push(nxt);
		R -= int64_t(nxt);
		L += int64_t(nxt);
	}
}

int32_t main(){
	ios_base::sync_with_stdio(false); 
	cin.tie(NULL); 
	
	int n, k;
	cin >> k >> n;

	vector<array<int, 2>> v;
	int64_t same = 0;

	for(int i = 0; i < n; i++){
		char a, b;
		int p, q;
		cin >> a >> p >> b >> q;
		if(a == b) same += abs(p - q);
		else v.push_back({p, q});
	}
	
	sort(v.begin(), v.end(), [](array<int, 2>& a, array<int, 2>& b){
		return (a[0] + a[1]) < (b[0] + b[1]);
	});

	n = v.size();
	same += n;

	L = R = 0;
	vector<int64_t> pref(n);
	for(int i = 0; i < n; i++){
		insert(v[i][0]);
		insert(v[i][1]);
		pref[i] = R - L;
	}

	int64_t ans = pref[n-1];
	if(k == 1){
		cout << same + ans << '\n';
		return 0;
	}

	while(!lpq.empty()) lpq.pop();
	while(!rpq.empty()) rpq.pop();

	L = R = 0;
	for(int i = 1; i < n; i++){
		insert(v[i][0]);
		insert(v[i][1]);

		ans = min(ans, pref[i-1] + R - L);
	}

	cout << same + ans << '\n';
	return 0; 
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 14
• Subtask 3: 0 / 9
• Subtask 4: 0 / 32
• Subtask 5: 0 / 37