# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
151704 | 2019-09-04T08:19:47 Z | willi19 | Friend (IOI14_friend) | C++14 | 0 ms | 0 KB |
#include "friend.h" #include<bits/stdc++.h> using namespace std; int c[100100],h[100100],p[100100],edge[12][12],dp[11000]; int ans(int state) { if(!dp[state]) return dp[state]; int ret=0; for(int i=0;i<n;i++) if(state&(1<<i)) ret+=c[i]; for(int i=0;i<n;i++) { if((state&(1<<i))==1) continue; bool pos=true; for(int j=0;j<n;j++) if(edge[i][j]==1) pos=false; if(pos) ret=max(ret,ans(state|(1<<i))); } dp[state]=ret; return ret; } int findSample(int n,int confidence[],int host[],int protocol[]){ for(int i=0;i<n;i++) { c[i]=confidence[i]; h[i]=host[i]; p[i]=protocol[i]; } for(int i=1;i<=n;i++) { if(p[i]==0) edge[i][h[i]]=edge[h[i]][i]=1; else { for(int j=0;j<n;j++) edge[i][j]=edge[h[i]][j]; if(p[i]==2) edge[i][host[i]]=edge[host[i]][i]=1; } } cout<<ans(0); }