Submission #521736

#	Time	Username	Problem	Language	Result	Execution time	Memory
521736		sidon	Palembang Bridges (APIO15_bridge)	C++17	100 / 100	59 ms	6088 KiB

bridge

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

int K, N, ext, ans, c, suf[1<<17];
vector<array<int, 2>> a;

priority_queue<int> L, R;

void put(int v) {
	if(empty(L) || v <= L.top())
		L.push(+v), c -= v;
	else
		R.push(-v), c += v;

	if(size(L) < size(R))
		L.push(v = -R.top()), R.pop(), c -= v*2;
	if(size(L) > size(R) + 1)
		R.push(v = -L.top()), L.pop(), c -= v*2;
}

int32_t main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> K >> N;

	for(int i = 0, s, t; i < N; ++i) {
		char p, q;
		cin >> p >> s >> q >> t;

		if(p == q) ext += abs(t - s);
		else
			++ext, a.push_back({s, t});
	}

	N = size(a);
	sort(begin(a), end(a) , [&](const auto &i, const auto &j) {
		return i[0] + i[1] < j[0] + j[1];
	});

	for(int i = N; i--; ) {
		put(a[i][0]), put(a[i][1]);
		ans = suf[i] = c;
	}

	if(K > 1) {
		L = R = priority_queue<int> (), c = 0;

		for(int i = 0; i < N; ++i) {
			put(a[i][0]), put(a[i][1]);
			ans = min(ans, c + suf[i+1]);
		}
	}

	cout << ans + ext;
}

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