Submission #1312695

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312695		053thousand	Palembang Bridges (APIO15_bridge)	C++20	22 / 100	199 ms	19188 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);
	}
	mii=f;
	bf=0;
	if(a==1){
		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=0;
		for(maa=ma.begin();maa!=ma.end();maa++){
			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: 8 / 8
• Subtask 2: 14 / 14
• Subtask 3: 0 / 9
• Subtask 4: 0 / 32
• Subtask 5: 0 / 37