Submission #1179136

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179136		alexander707070	Palembang Bridges (APIO15_bridge)	C++20	63 / 100	2093 ms	2264 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,toadd;

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

void solve_easy(){
	if(m==0){
		cout<<ans<<"\n";
		return;
	}

	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(){

	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;
}

void solve(int l,int r,int optl,int optr){
	if(l>r)return;

	int mid=(l+r)/2,opt;
	p=vals[mid];
	long long best=inf;

	for(int i=optl;i<=optr;i++){
		q=vals[i];
		long long curr=calc();

		if(curr<best){
			best=curr; opt=i;
		}
	}

	toadd=min(toadd,best);
	solve(l,mid-1,optl,opt);
	solve(mid+1,r,opt,optr);
}

void solve_hard(){
	if(m==0){
		cout<<ans<<"\n";
		return;
	}

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

	toadd=inf;
	solve(0,int(vals.size())-1,0,int(vals.size())-1);
	ans+=toadd;

	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: 8 / 8
• Subtask 2: 14 / 14
• Subtask 3: 9 / 9
• Subtask 4: 32 / 32
• Subtask 5: 0 / 37