2300: Calendar Colors
英語の時点で辛かった。ただ翻訳に投げて内容を掴めたら、NとMが小さいことからそれぞれの累乗和をあらかじめに計算しておき、後は全探索でなんとかなりそうってなって、なんとかなった。O(2^N)
double d(double a,double b){ return (a-b)*(a-b); } int main(){ int n,m; double a[20],b[20],c[20]; double fld[20][20]; cin>>n>>m; REP(i,n)cin>>a[i]>>b[i]>>c[i]; REP(i,n)REP(j,n){ fld[i][j]=d(a[i],a[j])+d(b[i],b[j])+d(c[i],c[j]); } double ans=0; REP(i,1<<n){ int cnt=0; vector<int>V; REP(j,n)if(i>>j&1){ cnt++; V.push_back(j); } if(cnt!=m)continue; double res=0; REP(j,m){ for(int k=j+1;k<m;k++){ res+=fld[V[j]][V[k]]; } } ans=max(ans,res); } printf("%.10f\n",ans); }