oj.uz

Submission #32180

# Submission time Handle Problem Language Result Execution time Memory
32180 2017-10-03T05:56:47 Z minchurl Palembang Bridges (APIO15_bridge) C++11
31 / 100
 2000 ms 3460 KB 
#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

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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3460 KB Output is correct
2 Correct 0 ms 3460 KB Output is correct
3 Correct 0 ms 3460 KB Output is correct
4 Correct 0 ms 3460 KB Output is correct
5 Correct 0 ms 3460 KB Output is correct
6 Correct 0 ms 3460 KB Output is correct
7 Correct 0 ms 3460 KB Output is correct
8 Correct 0 ms 3460 KB Output is correct
9 Correct 0 ms 3460 KB Output is correct
10 Correct 0 ms 3460 KB Output is correct
11 Correct 0 ms 3460 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3460 KB Output is correct
2 Correct 0 ms 3460 KB Output is correct
3 Correct 0 ms 3460 KB Output is correct
4 Correct 0 ms 3460 KB Output is correct
5 Correct 0 ms 3460 KB Output is correct
6 Correct 0 ms 3460 KB Output is correct
7 Correct 0 ms 3460 KB Output is correct
8 Correct 0 ms 3460 KB Output is correct
9 Correct 0 ms 3460 KB Output is correct
10 Correct 0 ms 3460 KB Output is correct
11 Correct 0 ms 3460 KB Output is correct
12 Correct 29 ms 3460 KB Output is correct
13 Correct 59 ms 3460 KB Output is correct
14 Correct 53 ms 3460 KB Output is correct
15 Correct 36 ms 3460 KB Output is correct
16 Correct 36 ms 3460 KB Output is correct
17 Correct 49 ms 3460 KB Output is correct
18 Correct 53 ms 3460 KB Output is correct
19 Correct 59 ms 3460 KB Output is correct
20 Correct 46 ms 3460 KB Output is correct
21 Correct 56 ms 3460 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3460 KB Output is correct
2 Correct 0 ms 3460 KB Output is correct
3 Correct 6 ms 3460 KB Output is correct
4 Correct 6 ms 3460 KB Output is correct
5 Correct 0 ms 3460 KB Output is correct
6 Correct 0 ms 3460 KB Output is correct
7 Correct 6 ms 3460 KB Output is correct
8 Correct 6 ms 3460 KB Output is correct
9 Correct 6 ms 3460 KB Output is correct
10 Correct 6 ms 3460 KB Output is correct
11 Correct 16 ms 3460 KB Output is correct
12 Correct 6 ms 3460 KB Output is correct

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3460 KB Output is correct
2 Correct 0 ms 3460 KB Output is correct
3 Correct 3 ms 3460 KB Output is correct
4 Correct 6 ms 3460 KB Output is correct
5 Correct 0 ms 3460 KB Output is correct
6 Correct 0 ms 3460 KB Output is correct
7 Correct 9 ms 3460 KB Output is correct
8 Correct 6 ms 3460 KB Output is correct
9 Correct 9 ms 3460 KB Output is correct
10 Correct 6 ms 3460 KB Output is correct
11 Correct 6 ms 3460 KB Output is correct
12 Correct 6 ms 3460 KB Output is correct
13 Execution timed out 2000 ms 3460 KB Execution timed out
14 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3460 KB Output is correct
2 Correct 0 ms 3460 KB Output is correct
3 Correct 6 ms 3460 KB Output is correct
4 Correct 6 ms 3460 KB Output is correct
5 Correct 0 ms 3460 KB Output is correct
6 Correct 0 ms 3460 KB Output is correct
7 Correct 9 ms 3460 KB Output is correct
8 Correct 9 ms 3460 KB Output is correct
9 Correct 6 ms 3460 KB Output is correct
10 Correct 6 ms 3460 KB Output is correct
11 Correct 9 ms 3460 KB Output is correct
12 Correct 6 ms 3460 KB Output is correct
13 Execution timed out 2000 ms 3460 KB Execution timed out
14 Halted 0 ms 0 KB -