제출 #533794

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
533794		new_acc	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	209 ms	14688 KiB

bridge

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=1e5+10;
struct st{
	int a,b,sr;
};
st t[N];
multiset<pair<int,int> > mu;
multiset<pair<int,int> >::iterator it;
ll summ,sumw;
int ilem,ilew,curr;
ll val1[N],val2[N];
void add(int x,int ind){
	mu.insert({x,ind});
	if(x>=curr) ilew++,sumw+=(ll)x;
	else summ+=(ll)x,ilem++;
	if(ilew>ilem){
		ilew--,ilem++;
		summ+=(ll)curr;
		it++;
		curr=(*it).fi;
		sumw-=(ll)curr;
	}else{
		if(ilem-1>ilew){
			ilem--,ilew++;
			sumw+=(ll)curr;
			it--;
			curr=(*it).fi;
			summ-=(ll)curr;
		}
	}
}	
void solve(){
	int n,k;
	cin>>k>>n;
	ll res=0;
	int l=0;
	for(int i=1;i<=n;i++){
		char a,c;
		int b,d;
		cin>>a>>b>>c>>d;
		if(a==c) res+=(ll)abs(d-b);
		else{
			res++;
			st pom;
			pom.a=b,pom.b=d,pom.sr=(b+d);
			t[++l]=pom;
		}
	}
	n=l;
	if(n==0){
		cout<<res<<"\n";
		return;
	}
	if(n==1){
		cout<<res+(ll)abs(t[1].a-t[1].b)<<"\n";
		return;
	}
	sort(t+1,t+1+n,[](st a,st b){
		return a.sr<b.sr;
	});
	mu.insert({t[1].a,1});
	curr=t[1].a;
	it=mu.begin();
	add(t[1].b,2);
	if(k==1){
		for(int i=2;i<=n;i++){
			add(t[i].a,i*2-1);
			add(t[i].b,i*2);
		}
		cout<<(ll)curr*(ll)ilem-summ+sumw-(ll)curr*(ll)ilew+res<<"\n";
	}else{
		val1[1]=(ll)curr*(ll)ilem-summ+sumw-(ll)curr*(ll)ilew;
		for(int i=2;i<=n;i++){
			add(t[i].a,i*2-1);
			add(t[i].b,i*2);
			val1[i]=(ll)curr*(ll)ilem-summ+sumw-(ll)curr*(ll)ilew;
		}
		sumw=0,summ=0,ilem=0,ilew=0,curr=0;
		mu.clear();
		mu.insert({t[n].a,1});
		curr=t[n].a;
		it=mu.begin();
		add(t[n].b,2);
		val2[n]=(ll)curr*(ll)ilem-summ+sumw-(ll)curr*(ll)ilew;
		for(int i=n-1;i>=1;i--){
			add(t[i].a,(n-i+1)*2-1);
			add(t[i].b,(n-i+1)*2);
			val2[i]=(ll)curr*(ll)ilem-summ+sumw-(ll)curr*(ll)ilew;
		}
		ll res2=LLONG_MAX;
		for(int i=1;i<=n-1;i++) res2=min(res2,val1[i]+val2[i+1]);
		cout<<res2+res<<"\n";
	}	
}
int main(){
	ios_base::sync_with_stdio(0),cin.tie(0);
	solve();
}

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