Submission #3709770

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
const int N=17;
double dis[N][N],f[1<<N],x[N],y[N],a[N]; 
int n,m;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>x[i]>>y[i]>>a[i];
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++) dis[i][j]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
	for(int i=0;i<=1<<n;i++) f[i]=1e18;
	f[0]=0;
	for(int i=0;i<n;i++) f[1<<i]=0;
	for(int s=0;s<1<<n;s++){
		for(int i=0;i<=n-1;i++)
			for(int j=0;j<=n-1;j++)
				if((s&(1<<i))&&(!(s&(1<<j)))) f[s|(1<<j)]=min(f[s|(1<<j)],f[s]+dis[i+1][j+1]);
	}
	for(int s=0;s<1<<n;s++){
		f[s]=-f[s];
		for(int i=0;i<n;i++)if(s&(1<<i)) f[s]+=a[i+1];
		f[s]/=__builtin_popcount(s);
		for(int t=(s-1)&s;t;t=(t-1)&s)
			f[s]=max(f[s],min(f[t],f[s-t]));
	}
	printf("%.10lf\n", f[(1<<n)-1]);
}

Submission Info

Judge Result