Submission #979690

#	Time	Username	Problem	Language	Result	Execution time	Memory
979690		tamir1	Palembang Bridges (APIO15_bridge)	C++17	22 / 100	31 ms	4996 KiB

bridge

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll ans,n,k,i,j,x,y,l,m,a[200005],z,mn=1e18;
array<ll,2> b[200005];
char s,t;
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> k >> n;
	for(i=1;i<=n;i++){
		cin >> s >> x >> t >> y;
		if(s==t) ans+=abs(x-y);
		else{
			ans++;
			l++;
			a[l]=x;
			l++;
			a[l]=y;
			m++;
			b[m][0]=x;
			b[m][1]=y;
		}
	}
	sort(a+1,a+l+1);
	x=a[(l+1)/2];
	//cout << x << " ";
	if(k==1){
	for(i=1;i<=l;i++){
		ans+=abs(x-a[i]);
	}
	cout << ans;
	return 0;}
	for(i=1;i<l;i++){
		for(j=i+1;j<=l;j++){
			z=0;
			for(ll g=1;g<=m;g++){
				z+=min(abs(a[i]-b[g][0])+abs(a[i]-b[g][1]),abs(a[j]-b[g][0])+abs(a[j]-b[g][1]));
			}
			mn=min(mn,z);
		}
	}
	cout << ans+mn;
}

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