Submission #1028582

#	Time	Username	Problem	Language	Result	Execution time	Memory
1028582		UmairAhmadMirza	Palembang Bridges (APIO15_bridge)	C++17	31 / 100	2089 ms	2572 KiB

bridge

#include <bits/stdc++.h>
using namespace std;
#define int long long
int const inf=1e16;
int k,n;
void solve(){
	vector<int> pos;
	int ans=0;
	vector<pair<int,int>> pr;
	for (int i = 0; i < n; ++i)
	{
		char a,b;
		int pa,pb;
		cin>>a>>pa>>b>>pb;
		if(a==b)
			ans+=abs(pa-pb);
		else{
			if(pa>pb)
				swap(pa,pb);
			pr.push_back({pa,pb});
			pos.push_back(pa);
			pos.push_back(pb);
		}
	}
	ans+=pr.size();
	int ans1=inf;
	if(pr.size()==0)
		ans1=0;
	for (auto b1:pos)
		for(auto b2:pos){
			if(b1>=b2)
				continue;
			int temp=0;
			for(auto p:pr)
				temp+=min( abs(b1-p.first)+abs(b1-p.second) , abs(b2-p.first)+abs(b2-p.second));
			ans1=min(ans1,temp);
		}
	cout<<ans+ans1<<endl;
}
signed main(){
	cin>>k>>n;
	if(k==2){
		solve();
		return 0;
	}
	vector<int> pos;
	int ans=0;
	int sm=0;
	for (int i = 0; i < n; ++i)
	{
		char a,b;
		int pa,pb;
		cin>>a>>pa>>b>>pb;
		if(a==b)
			ans+=abs(pa-pb);
		else{
			sm+=pa;
			sm+=pb;
			pos.push_back(pa);
			pos.push_back(pb);
		}
	}
	sort(pos.begin(), pos.end());
	int ex=0;
	int cnta=0;
	ans+=(pos.size())/2;
	int cntb=pos.size();
	int ans1=sm;
	for (auto i:pos)
	{
		// cout<<i<<' ';
		sm-=i;
		ex+=i;
		cnta++;
		cntb--;
		int temp=(i*cnta)-ex;
		temp+=sm-(i*cntb);
		// cout<<temp<<endl;
		ans1=min(ans1,temp);
	}
	cout<<ans+ans1<<endl;
	return 0;
}

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