Submission #871292

#	Time	Username	Problem	Language	Result	Execution time	Memory
871292		qthang2k11	Palembang Bridges (APIO15_bridge)	C++17	100 / 100	85 ms	6496 KiB

bridge

// [+] dinhmanhhungwillwinioi2024
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int N = 1e5 + 5;

int k, n;
ll ans = 0;

vector<pair<int, int>> arr;
ll pref[N], suf[N];

priority_queue<int> p1;
priority_queue<int, vector<int>, greater<int>> p2;
ll s1, s2;

void add(int x) {
	if (!p1.empty() && x < p1.top()) {
		p1.emplace(x);
		s1 += x;
	} else {
		p2.emplace(x);
		s2 += x;
	}
	
	while (p1.size() > p2.size()) {
		int val = p1.top();
		
		p1.pop();
		s1 -= val;
		
		p2.emplace(val);
		s2 += val;
	}
	
	while (p2.size() > p1.size()) {
		int val = p2.top();
		
		p2.pop();
		s2 -= val;
		
		p1.emplace(val);
		s1 += val;
	}
}

inline ll cost() {
	int med = p1.top();
	return (1LL * med * p1.size() - s1) + (s2 - 1LL * med * p2.size());
}

void calc(ll dp[], bool rev) {
	while (!p1.empty()) p1.pop();
	while (!p2.empty()) p2.pop();
	s1 = s2 = 0;
	
	int m = arr.size();
	
	for (int i = 1; i <= m; i++) {
		add(arr[i - 1].first);
		add(arr[i - 1].second);
		dp[i] = cost();
	}
	
	if (rev) {
		reverse(dp + 1, dp + m + 1);
	}
}

int32_t main() {
	cin.tie(0)->sync_with_stdio(0);
	
	cin >> k >> n;
	for (int i = 1; i <= n; i++) {
		char c1, c2;
		int p1, p2;
		cin >> c1 >> p1 >> c2 >> p2;
		if (c1 == c2) {
			ans += abs(p1 - p2);
		} else {
			arr.emplace_back(p1, p2);
		}
	}
	
	sort(arr.begin(), arr.end(), [&] (const pair<int, int> &x, const pair<int, int> &y) {
		return x.first + x.second < y.first + y.second;
	});
	
	calc(pref, false);
	reverse(arr.begin(), arr.end());
	calc(suf, true);
	
	if (k == 1) {
		ans += pref[arr.size()];
	} else {
		int m = arr.size();
		ll res = ans + pref[m];
		for (int i = 1; i < m; i++)
			res = min(res, ans + pref[i] + suf[i + 1]);
		ans = res;
	}
	
	cout << ans + arr.size();
	
	return 0;
}

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