Submission #981903

#	Time	Username	Problem	Language	Result	Execution time	Memory
981903		michified	Palembang Bridges (APIO15_bridge)	C++17	22 / 100	46 ms	4560 KiB

bridge

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

ll ltot, rtot;
priority_queue<int> pql;
priority_queue<int, vector<int>, greater<int>> pqr;

void put(ll x) {
	ll med = pql.empty() ? LLONG_MAX : pql.top(), tmp;
	if (x <= med) {
		pql.push(x);
		ltot += x;
	} else {
		pqr.push(x);
		rtot += x;
	}
	if (pqr.size() + 1 < pql.size()) {
		tmp = pql.top();
		pql.pop();
		pqr.push(tmp);
		ltot -= tmp;
		rtot += tmp;
	} else if (pqr.size() > pql.size()) {
		tmp = pqr.top();
		pqr.pop();
		pql.push(tmp);
		ltot += tmp;
		rtot -= tmp;
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int k, n, i;
	cin >> k >> n;
	char az, bz;
	ll ap, bp, ss = 0, best = 0;
	vector<ll> pos;
	vector<pair<ll, ll>> ppl;
	for (i = 0; i < n; i++) {
		cin >> az >> ap >> bz >> bp;
		if (az == bz) ss += abs(ap - bp);
		else {
			if (ap > bp) swap(ap, bp);
			ppl.push_back({ap, bp});
			ss++;
		}
	}
	n = ppl.size();
	sort(ppl.begin(), ppl.end(), [](const pair<int, int>& one, const pair<int, int>& two){return one.first + one.second < two.first + two.second;});
	ltot = rtot = 0;
	vector<ll> pref(n + 1);
	for (i = 0; i < n; i++) {
		put(ppl[i].first);
		put(ppl[i].second);
		pref[i + 1] = rtot - ltot;
	}
	best = pref[n];

	if (k == 2) {
		while (not pql.empty()) pql.pop();
		while (not pqr.empty()) pqr.pop();
		ltot = rtot = 0;
		for (i = 0; i < n; i++) {
			put(ppl[i].first);
			put(ppl[i].second);
			best = min(best, rtot - ltot + pref[i]);
		}
	}
	cout << ss + best;
	return 0;
}

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