Submission #1257306

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257306		MasterDebater	Palembang Bridges (APIO15_bridge)	C++20	100 / 100	209 ms	12112 KiB

bridge

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<ll,ll>
#define F first
#define S second
const int N=1e5+10;
ll n,k,ans,tmp,lsum,rsum,pref[N];
vector<pii>v;
multiset<ll>l,r;
bool cmp(pii a,pii b){
	return a.F+a.S<b.F+b.S;
}
void add(ll x){
	if(l.empty() or x<=(*--l.end()))l.insert(x),lsum+=x;
	else r.insert(x),rsum+=x;
	if(l.size()-1>=r.size()+1){
		ll y=(*--l.end());
		r.insert(y);
		l.erase(--l.end());
		rsum+=y;
		lsum-=y;
	}
	if(r.size()>l.size()){
		ll y=(*r.begin());
		l.insert(y);
		r.erase(r.begin());
		lsum+=y;
		rsum-=y;
	}
	return;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin>>k>>n;
	for(int i=0;i<n;i++){
		char a,b;
		ll x,y;
		cin>>a>>x>>b>>y;
		if(a==b)ans+=abs(x-y);
		else v.push_back({x,y});
	}
	n=v.size();
	ans+=n;
	sort(v.begin(),v.end(),cmp);
	for(int i=0;i<n;i++){
		add(v[i].F);
		add(v[i].S);
		pref[i+1]=rsum-lsum;
	}
	tmp=pref[n];
	if(k==2){
		l.clear();
		r.clear();
		lsum=rsum=0;
		for(int i=n-1;i>=0;i--){
			add(v[i].F);
			add(v[i].S);
			tmp=min(tmp,rsum-lsum+pref[i]);
		}
	}
	cout<<tmp+ans;
	return 0;
}

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