제출 #443596

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
443596		8e7	Palembang Bridges (APIO15_bridge)	C++17	100 / 100	165 ms	7512 KiB

bridge

//Challenge: Accepted
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <utility>
#include <assert.h>
using namespace std;
void debug() {cout << endl;}
template <class T, class ...U> void debug(T a, U ... b) { cout << a << " "; debug(b...);}
template <class T> void pary(T l, T r) {
	while (l != r) {cout << *l << " ";l++;}
	cout << endl;
}
#define ll long long
#define ld long double
#define maxn 100005
#define pii pair<int, int>
#define pdd pair<double, double>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
pii a[maxn], b[maxn];
ll pref[maxn], suf[maxn];
void solve(int n, pii arr[], ll ans[]) {
	ll lc = 0, rc = 0, cur = 0, cost = 0;
	priority_queue<pii, vector<pii>, greater<pii> > pq;
	for (int i = 0;i < n;i++) {
		if (arr[i].ff > cur) pq.push({arr[i].ff, 0}), rc++, cost += arr[i].ff - cur;	
		pq.push({arr[i].ss, 1});
		while (pq.size()) {
			pii seg = pq.top();pq.pop();
			ll dis = seg.ff - cur;
			if (dis == 0 || (lc - rc) * dis < 0) {
				cost += (lc - rc) * dis;
				cur = seg.ff;
				if (seg.ss == 0) rc--;
				else lc++;
			} else {
				pq.push(seg);
				break;
			}
		}
		ans[i] = cost;
	}
}
int main() {
	int k, n;
	cin >> k >> n;
	int cross = 0;
	ll sum = 0;
	int m = 0, ma = 0;
	for (int i = 0;i < n;i++) {
		char p, q;
		int s, t;
		cin >> p >> s >> q >> t;
		if (s > t) swap(s, t);
		sum += t - s;
		ma = max(ma, t);
		if (p != q) {
			a[m++] = {s, t};	
		}
	}
	sort(a, a + m, [&](pii x, pii y) {return x.ff + x.ss < y.ff + y.ss;});
	solve(m, a, pref);
	ll ans = pref[m - 1];
	if (k == 2) {
		for (int i = 0;i < m;i++) {
			b[i] = a[m - 1 - i];
			b[i] = {ma - b[i].ss, ma - b[i].ff};
		}
		solve(m, b, suf);
		ans = min(pref[m - 1], suf[m - 1]);
		for (int i = 0;i < m - 1;i++) {
			ans = min(ans, pref[i] + suf[m - 2 - i]);
		}
	}
	cout << 2 * ans + sum + m << endl;
}
/*
1 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7

2 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7
   */

컴파일 시 표준 에러 (stderr) 메시지

bridge.cpp: In function 'int main()':
bridge.cpp:51:6: warning: unused variable 'cross' [-Wunused-variable]
   51 |  int cross = 0;
      |      ^~~~~

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