제출 #1192036

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1192036		Tsagana	Palembang Bridges (APIO15_bridge)	C++20	100 / 100	52 ms	5520 KiB

bridge

#include <bits/stdc++.h>

#define IOS ios_base::sync_with_stdio(false);cin.tie();cout.tie();
#define all(x, y) x.begin(), x.begin() + y
#define int long long
#define pq priority_queue
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define pp pop_back
#define F first
#define S second

using namespace std;

struct pii {
	int l, r;
	bool operator<(pii b) const { return l + r < b.l + b.r; }
};

void solve () {
	int k, n, m = 0;
	cin >> k >> n;
	vector<pii> v(n);
	vector<int> a(n);
	int s = 0, w = 0;
	for (int l, r, i = 0; i < n; i++) {
		char c, h;
		cin >> c >> l >> h >> r;
		if (l > r) swap(l, r);
		if (c != h) v[m++] = {l, r};
		else s += r - l;
	}
	s += n = m;
	sort(all(v, n));

	pq<int> L, R;

	auto add = [&](pii p) {
		L.push(p.l);
		R.push(-p.r);
		w += p.r - p.l;
		if (L.top() > -R.top()) {
			int l = L.top(); 
			int r = -R.top();
			L.pop();
			R.pop();
			L.push(r);
			R.push(-l);
			w += (l - r) * 2;
		}
		return w;
	};

	for (int i = 0; i < n; i++) a[i] = add(v[i]);
	w = 0;
	pq<int> ().swap(L);
	pq<int> ().swap(R);
	int t = n ? a[n-1] : 0;
	if (n && k == 2) for (int i = n; --i;) t = min(t, add(v[i]) + a[i-1]);
	cout << s + t;
}
signed main() {IOS solve(); return 0;}

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