Submission #737919

#	Time	Username	Problem	Language	Result	Execution time	Memory
737919		boyliguanhan	Palembang Bridges (APIO15_bridge)	C++17	100 / 100	73 ms	6108 KiB

bridge

#include <bits/stdc++.h>
#define int long long
using namespace std;
#define PQ priority_queue
#define PQG(x) PQ<x,vector<x>,greater<x>>
bool cmp(pair<int, int> a, pair<int, int> b) {
	return a.first + a.second < b.first + b.second;
}
PQ<int> l;
PQG(int) r;
int ls, rs, arr[100100];
void ins(int x) {
	int m = (l.size() ? l.top() : (int)(1e9+7));
	if (x <= m) {
		l.push(x);
		ls += x;
	} else {
		r.push(x);
		rs += x;
	}
	if (r.size() + 1 < l.size()) {
		int x = l.top();
		l.pop();
		r.push(x);
		ls -= x;
		rs += x;
	} else if (l.size() < r.size()) {
		int x = r.top();
		r.pop();
		l.push(x);
		rs -= x;
		ls += x;
	}
}
signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int k, n;
	int ans = 0;
	vector<pair<int, int>> v = {{0, 0}};
	cin >> k >> n;
	for(int i = 0; i < n; i++){
		char a, b;
		int x, y;
		cin >> a >> x >> b >> y;
		if (a == b) ans += abs(x - y);
		else v.push_back({x, y});
	}
	sort(v.begin(), v.end(), cmp);
	ans += n = v.size()-1;
	for(int i = 1; i <= n; i++) {
		ins(v[i].first);
		ins(v[i].second);
		arr[i] = rs - ls;
	}
	int ans2 = arr[n];
	if (k == 2) {
		l = PQ<int>();
        r = PQG(int)();
		ls = rs = 0;
		for (int i = n+1; --i;) {
			ins(v[i].first);
			ins(v[i].second);
			ans2 = min(ans2, rs - ls + arr[i - 1]);
		}
	}
	cout << ans + ans2;
	return 0;
}

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