Submission #1179127

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179127		alexander707070	Palembang Bridges (APIO15_bridge)	C++20	0 / 100	0 ms	324 KiB

bridge

#include<bits/stdc++.h>
#define MAXN 100007
using namespace std;

const long long inf=1e17;

struct house{
	int x,y;
};

int n,k,x,y,m,p,q;
long long ans;

char s,t;
house h[MAXN];
vector<int> vals;

void solve_easy(){

	int pos=vals[m];
	for(int i=1;i<=m;i++){
		ans+=abs(pos-h[i].x);
		ans+=abs(pos-h[i].y);
		ans++;
	}

	cout<<ans<<"\n";
}

long long calc(int id){
	q=vals[id];

	long long sum=0;
	for(int i=1;i<=m;i++){
		sum+=min( abs(h[i].x-p)+abs(h[i].y-p) , abs(h[i].x-q)+abs(h[i].y-q) )+1;
	}

	return sum;
}

long long bin(int s){
	int l=s,r=vals.size()-1,tt;

	while(l+1<r){
		tt=(l+r)/2;

		if(calc(tt)>calc(tt+1)){
			l=tt+1;
		}else{
			r=tt;
		}
	}

	long long res=calc(l);
	for(int i=max(s,l-2);i<=min(2*m-1,l+2);i++){
		res=min(res,calc(i));
	}

	return res;
}

void solve_hard(){
	vals.erase( unique( vals.begin(), vals.end() ), vals.end() );
	sort(vals.begin(),vals.end());

	long long best=inf;
	for(int i=0;i<vals.size();i++){
		p=vals[i];
		
		long long res=bin(i);
		best=min(best,res);
	}

	ans+=best;
	cout<<ans<<"\n";
}

int main(){

	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin>>k>>n;
	for(int i=1;i<=n;i++){
		cin>>s>>x>>t>>y;
		
		if(s==t){
			ans+=abs(x-y);
			continue;
		}

		m++; h[m]={x,y};
	}

	for(int i=1;i<=m;i++){
		vals.push_back(h[i].x);
		vals.push_back(h[i].y);
	}

	sort(vals.begin(),vals.end());

	if(k==1){
		solve_easy();
	}else{
		solve_hard();
	}

	return 0;
}

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