제출 #959494

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
959494		MinaRagy06	Palembang Bridges (APIO15_bridge)	C++17	100 / 100	62 ms	6708 KiB

bridge

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define sz(x) (int) x.size()

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	int k, n;
	cin >> k >> n;
	ll ans = 0;
	vector<array<int, 2>> a;
	for (int i = 0; i < n; i++) {
		char t1, t2;
		int l, r;
		cin >> t1 >> l >> t2 >> r;
		if (t1 == t2) {
			ans += abs(l - r);
			continue;
		}
		if (l > r) swap(l, r);
		a.push_back({l, r});
	}
	n = a.size();
	if (k == 1) {
		vector<ll> v;
		for (int i = 0; i < n; i++) {
			v.push_back(a[i][0]);
			v.push_back(a[i][1]);
		}
		sort(v.begin(), v.end());
		for (int i = 0; i < sz(v); i++) {
			ans += abs(v[i] - v[sz(v) / 2]);
		}
		cout << ans + sz(a) << '\n';
		return 0;
	}
	sort(a.begin(), a.end(), [&] (array<int, 2> x, array<int, 2> y) {return x[0] + x[1] < y[0] + y[1];});
	auto process = [&] (vector<int> &order, ll arr[]) {
		ll sumL = 0, sumR = 0;
		priority_queue<int> pqL;
		priority_queue<int, vector<int>, greater<>> pqR;
		for (auto i : order) {
			pqL.push(a[i][0]);
			sumL += a[i][0];
			pqL.push(a[i][1]);
			sumL += a[i][1];
			while (pqL.size() > pqR.size()) {
				int x = pqL.top();
				pqL.pop();
				sumL -= x;

				pqR.push(x);
				sumR += x;
			}
			while (pqL.top() > pqR.top()) {
				int x = pqL.top(), y = pqR.top();
				pqL.pop();
				sumL -= x;
				pqR.pop();
				sumR -= y;

				pqL.push(y);
				sumL += y;
				pqR.push(x);
				sumR += x;
			}
			assert(pqL.size() == pqR.size());
			arr[i] = sumR - sz(pqR) * pqL.top();
			arr[i] += sz(pqL) * pqL.top() - sumL;
		}
	};
	ll prf[n + 1]{}, suf[n + 1]{};
	vector<int> order(n);
	for (int i = 0; i < n; i++) {
		order[i] = n - 1 - i;
	}
	process(order, suf);
	for (int i = 0; i < n; i++) {
		order[i] = i;
	}
	process(order, prf);
	ll mn = suf[0];
	for (int i = 0; i < n; i++) {
		mn = min(mn, prf[i] + suf[i + 1]);
	}
	ans += mn;
	cout << ans + sz(a) << '\n';
	return 0;
}

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