Submission #35636682

Source Code Expand

#include<stdio.h>
#include<math.h>
#define bit(x,i)(((x)>>(i))&1)

double x[20],y[20];
double dp[17][1<<17];
int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=0;i<n+m;i++)scanf("%lf%lf",x+i,y+i);
	for(int i=0;i<n+m;i++)for(int s=0;s<1<<(n+m);s++)dp[i][s]=1e18;
	for(int i=0;i<n+m;i++)dp[i][1<<i]=hypot(x[i],y[i]);
	
	for(int s=1;s<1<<(n+m);s++){
		double coef=pow(0.5,__builtin_popcount(s>>n));
		for(int i=0;i<n+m;i++)if(bit(s,i)){
			for(int j=0;j<n+m;j++)if(!bit(s,j)){
				dp[j][s^(1<<j)]=fmin(dp[j][s^(1<<j)],dp[i][s]+hypot(x[i]-x[j],y[i]-y[j])*coef);
			}
		}
	}
	
	double ans=1e18;
	for(int i=0;i<n+m;i++)for(int s=(1<<n)-1;s<1<<(n+m);s+=1<<n)ans=fmin(ans,dp[i][s]+hypot(x[i],y[i])*pow(0.5,__builtin_popcount(s>>n)));
	printf("%.10f\n",ans);
}

Submission Info

Submission Time
Task E - Booster
User kyopro_friends
Language C (GCC 9.2.1)
Score 500
Code Size 782 Byte
Status AC
Exec Time 192 ms
Memory 19976 KiB

Compile Error

./Main.c: In function ‘main’:
./Main.c:9:2: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]
    9 |  scanf("%d%d",&n,&m);
      |  ^~~~~~~~~~~~~~~~~~~
./Main.c:10:24: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]
   10 |  for(int i=0;i<n+m;i++)scanf("%lf%lf",x+i,y+i);
      |                        ^~~~~~~~~~~~~~~~~~~~~~~

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 500 / 500
Status
AC × 3
AC × 23
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, random_20.txt, sample_01.txt, sample_02.txt, sample_03.txt
Case Name Status Exec Time Memory
random_01.txt AC 189 ms 19976 KiB
random_02.txt AC 7 ms 2868 KiB
random_03.txt AC 190 ms 19844 KiB
random_04.txt AC 2 ms 2528 KiB
random_05.txt AC 192 ms 19832 KiB
random_06.txt AC 6 ms 2752 KiB
random_07.txt AC 10 ms 2560 KiB
random_08.txt AC 92 ms 10636 KiB
random_09.txt AC 184 ms 19848 KiB
random_10.txt AC 22 ms 4280 KiB
random_11.txt AC 13 ms 3024 KiB
random_12.txt AC 4 ms 2652 KiB
random_13.txt AC 186 ms 19844 KiB
random_14.txt AC 182 ms 19836 KiB
random_15.txt AC 45 ms 6336 KiB
random_16.txt AC 6 ms 2348 KiB
random_17.txt AC 191 ms 19832 KiB
random_18.txt AC 2 ms 2452 KiB
random_19.txt AC 9 ms 2632 KiB
random_20.txt AC 1 ms 2128 KiB
sample_01.txt AC 1 ms 2132 KiB
sample_02.txt AC 1 ms 2296 KiB
sample_03.txt AC 1 ms 2220 KiB