Submission #32180

#	Time	Username	Problem	Language	Result	Execution time	Memory
32180		minchurl	Palembang Bridges (APIO15_bridge)	C++11	31 / 100	2000 ms	3460 KiB

bridge

#include<stdio.h>
#include<math.h>
#include<algorithm>
#define MAX_N 100005
#define abs(x) ((x)>0?(x):(-(x)))
#define LL long long
using namespace std;
struct emp{
	int x,y;
};
emp arr[MAX_N];
LL N,K;
LL only_arr[2*MAX_N],ans;
LL input(){
	LL i,n,S,T,sum=0;
	char P[2],Q[2];
	n=0;
	for(i=0;i<N;i++){
		scanf("%s %lld %s %lld",P,&S,Q,&T);
		if(P[0]==Q[0]){
			sum+=abs(S-T);
		}else{
			only_arr[2*n+1]=S;only_arr[2*n+2]=T;
			arr[++n].x=S;arr[n].y=T;
			sum++;
		}
	}
	N=n;
	return sum;
}
LL bridge_only(){
	LL i,x,sum=0;
	sort(only_arr+1,only_arr+2*N+1);
	x=N;
	for(i=1;i<=2*N;i++)	sum+=abs(only_arr[i]-only_arr[x]);
	return sum;
}
LL cost(LL x,LL y,LL P,LL Q){
	LL i,p,q,sum=0;
	for(i=1;i<=N;i++){
		if(i==x || i==y)	continue;
		p=abs(P-arr[i].x)+abs(P-arr[i].y);
		q=abs(Q-arr[i].x)+abs(Q-arr[i].y);
		p=p<q?p:q;
		sum+=p;
	}
	return sum;
}
LL proper(LL x,LL y){
	LL p,q,r,s;
	p=cost(x,y,arr[x].x,arr[y].x);
	q=cost(x,y,arr[x].x,arr[y].y);
	r=cost(x,y,arr[x].y,arr[y].x);
	s=cost(x,y,arr[x].y,arr[y].y);
	p=p<q?p:q;
	r=r<s?r:s;
	p=p<r?p:r;
	return abs(arr[x].x-arr[x].y)+abs(arr[y].x-arr[y].y)+p;
}
int main(){
	LL base;
	scanf("%lld %lld",&K,&N);
	base=input();
	ans=bridge_only()+base;
	if(K==1){
		printf("%lld\n",ans);
		return 0;
	}
	//O(N^3)
	LL i,j,k,x;
	for(i=1;i<=N;i++){
		for(j=i+1;j<=N;j++){
			x=proper(i,j)+base;
			ans=ans<x?ans:x;
		}
	}
	printf("%lld\n",ans);
	return 0;
}

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:70:9: warning: unused variable 'k' [-Wunused-variable]
  LL i,j,k,x;
         ^
bridge.cpp: In function 'long long int input()':
bridge.cpp:19:37: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s %lld %s %lld",P,&S,Q,&T);
                                     ^
bridge.cpp: In function 'int main()':
bridge.cpp:62:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld",&K,&N);
                          ^

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