제출 #1312451

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1312451		053thousand	Palembang Bridges (APIO15_bridge)	C++20	0 / 100	1 ms	572 KiB

bridge

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
	int a,b,c,d,e=0,f=0,ans=0,mii=1e18,bf,esf=0;
	map<int,int>ma,en;
	map<int,int>::iterator maa,maaa;
	char ch1,ch2;
	cin>>a>>b;
	for(int i=0;i<b;i++){
		cin>>ch1>>c>>ch2>>d;
		if(ch1!=ch2){
			if(c>d) swap(c,d);
			ma[c]+=2;
			ma[d]+=2;
			en[d]+=1;
			f+=c*2;
			e-=2;
			ans++;
		}
		ans+=abs(d-c);
	}
	f+=(ma.begin()->first)*e;
//	cout<<ans<<endl;
	if(a==1){
		bf=ma.begin()->first;
		for(maa=ma.begin();maa!=ma.end();maa++){
			f+=(maa->first-bf)*e;
			e+=maa->second;
			mii=min(mii,f);
			bf=maa->first;
		}
	}
	else{
		bf=ma.begin()->first;
		for(maa=ma.begin();maa!=ma.end();maa++){
//			cout<<1;
			f+=(maa->first-bf)*e;
			e+=maa->second;
			esf+=en[maa->first];
			int tempe=e,tempf=f,tempbf=maa->first;
			tempe-=esf*2;
			maaa=maa;
			maaa++;
			for(maaa=maaa;maaa!=ma.end();maaa++){
				tempf+=(maaa->first-tempbf)*tempe;
				tempe+=maaa->second;
				tempbf=maaa->first;
				mii=min(mii,tempf);
			}
			bf=maa->first;
		}
	}
	cout<<mii+ans;
}

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