Submission #1126561

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126561		ssitaram	Palembang Bridges (APIO15_bridge)	C++20	22 / 100	77 ms	9972 KiB

bridge

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

typedef long long ll;

struct med {
	ll as, bs;
	priority_queue<int> a;
	priority_queue<int, vector<int>, greater<int>> b;

	med() : as(0), bs(0) {}

	void resz() {
		while (a.size() >= b.size() + 2) {
			int e = a.top();
			as -= e;
			a.pop();
			b.push(e);
			bs += e;
		}
		while (a.size() < b.size()) {
			int e = b.top();
			bs -= e;
			b.pop();
			a.push(e);
			as += e;
		}
	}

	void add(int v) {
		if (a.empty() || v < a.top()) {
			a.push(v);
			as += v;
		} else {
			b.push(v);
			bs += v;
		}
		resz();
	}

	ll ans() {
		return ((ll) a.top() * a.size()) - as + bs - ((ll) a.top() * b.size());
	}
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int k, n; cin >> k >> n;
	ll ans = 0;
	vector<vector<int>> route = {{}};
	for (int i = 0; i < n; ++i) {
		char ac, bc;
		int a, b;
		cin >> ac >> a >> bc >> b;
		if (ac == bc) {
			ans += abs(b - a);
		} else {
			route.push_back({a + b, a, b});
		}
	}
	n = route.size() - 1;
	if (n == 0) {
		cout << ans << '\n';
		return 0;
	}
	route.push_back({});
	sort(next(route.begin()), prev(prev(route.end())));
	vector<ll> pref(n + 1);
	pref[0] = 0;
	med m1;
	for (int i = 1; i <= n; ++i) {
		m1.add(route[i][1]);
		m1.add(route[i][2]);
		pref[i] = m1.ans();
	}
	vector<ll> suff(n + 2);
	suff[n + 1] = 0;
	med m2;
	for (int i = n; i >= 1; --i) {
		m2.add(route[i][1]);
		m2.add(route[i][2]);
		suff[i] = m2.ans();
	}
	if (k == 1) {
		cout << pref[n] + ans + n << '\n';
	} else {
		ll best = INT64_MAX;
		for (int i = 0; i <= n; ++i) {
			best = min(best, pref[i] + suff[i + 1]);
		}
		cout << best + ans + n << '\n';
	}
	return 0;
}

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