Submission #414817

#	Time	Username	Problem	Language	Result	Execution time	Memory
414817		ngpin04	Palembang Bridges (APIO15_bridge)	C++14	41 / 100	74 ms	3600 KiB

bridge

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
using namespace std;
const int N = 1e5 + 5; 

long long pre[N];
long long suf[N];
long long lsum, rsum;

pair <int, int> a[N];

int n,m,k;

priority_queue <int> lheap, rheap;

void add(int x) {
	int med = (lheap.size() ? lheap.top() : 1e9 + 1);
	if (x <= med) {
		lheap.push(x);
		lsum += x;
		if (lheap.size() == rheap.size() + 2) {
			x = lheap.top();
			lsum -= x;
			rsum += x;
			lheap.pop();
			rheap.push(x);
		}
	} else {	
		rheap.push(-x);
		rsum += x;
		if (lheap.size() < rheap.size()) {
			x = -rheap.top();
			rsum -= x;
			lsum += x;
			rheap.pop();
			lheap.push(x);
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> k >> n;
	long long same_side = 0;
	for (int i = 1; i <= n; i++) {	
		char cx, cy;
		int x, y;
		cin >> cx >> x >> cy >> y;
		if (cx == cy)
			same_side += abs(x - y);
		else {
			if (x > y)
				swap(x, y);
			a[++m] = mp(x, y);
		}
	}	

	sort(a + 1, a + m + 1, [](pair <int, int> a, pair <int, int> b) {
		return (a.fi + a.se < b.fi + b.se);
	});
	
	for (int i = 1; i <= m; i++) {
		add(a[i].fi);
		add(a[i].se);
		assert(lheap.size() == rheap.size());
		pre[i] = rsum - lsum;
	}

	lsum = rsum = 0;
	while (lheap.size())
		lheap.pop();
	while (rheap.size())
		rheap.pop();

	for (int i = m; i >= 1; i--) {
		add(a[i].fi);
		add(a[i].se);
		assert(lheap.size() == rheap.size());
		suf[i] = rsum - lsum;
	}

	long long res = 1e18;
	for (int i = 0; i <= m; i++) 
		res = min(res, pre[i] + suf[i + 1]);
	if (k == 1)
		res = pre[m];
	cout << res + same_side + m;
	return 0;
}

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