Submission #489181

#	Time	Username	Problem	Language	Result	Execution time	Memory
489181		s_samchenko	Palembang Bridges (APIO15_bridge)	C++17	0 / 100	4 ms	8140 KiB

bridge

#include <bits/stdc++.h>
#include <ext/pb_ds/detail/standard_policies.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
//#pragma GCC optimize("Ofast")
//#pragma GCC target ("avx2")
#define ll long long
#define ff first
#define ss second
#define int ll
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define pb push_back
#define pii pair <int, int>
#define pdd pair <double, double>
using namespace std;
using namespace __gnu_pbds;
template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
const int inf = 1e15;
const int mod = 1e9+7;
const int N = 1e6+1010;

multiset <int> s1, s2;
int lsum = 0, rsum = 0;

void insert(int v){
	int median = s1.empty() ? inf : *s1.rbegin();
	if (v <= median){
		s1.insert(v);
		lsum += v;
	}
	else{
		s2.insert(v);
		rsum += v;
	}
	
	if (s2.size() + 1 < s1.size()){
		int nxt = *s1.rbegin();
		s1.erase(s1.find(nxt));
		s2.insert(nxt);
		lsum -= nxt;
		rsum += nxt;
	}
	else if (s1.size() < s2.size()) {
		int nxt = *s2.begin();
		s2.erase(s2.begin());
		s1.insert(nxt);
		rsum -= nxt;
		lsum += nxt;
	}
}

bool cmp(pii a, pii b){
	return a.ff + a.ss < b.ff + b.ss;
}

void solve(){
	int k, n, ans = 0;
	cin >> k >> n;
	
	vector <pii> a = {{0, 0}};
	for (int i = 0; i < n; ++i){
		char c1, c2;
		int x, y;
		cin >> c1 >> x >> c2 >> y;
		if (c1 == c2){
			ans += abs(x-y);
			continue;
		}
		if (x > y) swap(x, y);
		a.pb({x, y});
	}
	n = a.size() - 1;
	ans += n;
	
	if (k == 1){
		vector <int> b;
		for (auto i : a){
			b.pb(i.ff);
			b.pb(i.ss);
		}
		sort(all(b));
		for (int i = 0; i < n; ++i) ans -= b[i];
		for (int i = n; i < 2*n; ++i) ans += b[i];
		
		cout << ans;
		return;
	}
	sort(all(a), cmp);
	
	vector <int> p(N);
	for (int i = 0; i <= n; ++i){
		insert(a[i].ff);
		insert(a[i].ss);
		p[i] = rsum - lsum;
	}
	
	int res = p[n];
	while (s1.size()) s1.erase(s1.begin());
	while (s2.size()) s2.erase(s2.begin());
	lsum = rsum = 0;
	
	for (int i = n; i > 0; --i){
		insert(a[i].ff);
		insert(a[i].ss);
		res = min(res, rsum - lsum + p[i - 1]);
	}
	
	cout << ans + res;
}

signed main(){
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int tt = 1;
	//cin >> tt;
	while (tt--){
		solve();
		cout << '\n';
	}
}

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