제출 #228979

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
228979		alishahali1382	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	84 ms	9568 KiB

bridge

#include <bits/stdc++.h>
#pragma GCC optimize ("O2")
#pragma GCC optimize ("unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;

const ld eps=1e-7;
const int inf=1000000010;
const ll INF=10000000000000010LL;
const int mod=1000000007;
const int MAXN=100010, LOG=20;

ll n, m, k, u, v, x, y, t, l, r, ans, constant;
pll A[MAXN];
ll B[MAXN], C[MAXN];

struct Solver{
	priority_queue<ll> pref;
	priority_queue<ll, vector<ll>, greater<ll>> suff;
	ll pref_sum=0, suff_sum=0, mid=inf;
	
	void Add(ll x){
		if (x<=mid) pref.push(x), pref_sum+=x;
		else suff.push(x), suff_sum+=x;
		while (pref.size()<suff.size()){
			ll x=suff.top();
			suff.pop();
			suff_sum-=x;
			
			pref.push(x);
			pref_sum+=x;
			//cerr<<"move2 "<<x<<endl;
		}
		while (pref.size()-suff.size()>1){
			ll x=pref.top();
			pref.pop();
			pref_sum-=x;
			
			suff.push(x);
			suff_sum+=x;
			//cerr<<"move1 "<<x<<endl;
		}
		mid=pref.top();
	}
	ll Get(){
		return suff_sum-suff.size()*mid + pref.size()*mid-pref_sum;
	}
	
} S1, S2;

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	cin>>k>>m;
	//assert(m<=1000 && k==1);
	char c1, c2;
	while (m--){
		cin>>c1>>l>>c2>>r;
		if (l>r) swap(l, r);
		if (c1!=c2){
			A[++n]={l, r};
			constant++;
		}
		else constant+=r-l;
	}
	
	sort(A+1, A+n+1, [](pll i, pll j){
		return i.first+i.second<j.first+j.second;
	});
	
	for (int i=1; i<=n; i++){
		S1.Add(A[i].first);
		S1.Add(A[i].second);
		B[i]=S1.Get();
	}
	for (int i=n; i; i--){
		S2.Add(A[i].first);
		S2.Add(A[i].second);
		C[i]=S2.Get();
	}
	ans=B[n];
	if (k==2){
		for (int i=1; i<n; i++) ans=min(ans, B[i]+C[i+1]);
	}
	//debug(ans)
	cout<<ans+constant<<'\n';
	
	return 0;
}
/*
1 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7

*/

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