fork(18) download
  1. #include<iostream>
  2. #include<math.h>
  3. #include<algorithm>
  4. #include<stdio.h>
  5. #include<map>
  6. #include<vector>
  7. #include<set>
  8. #include<iomanip>
  9. #define F first
  10. #define S second
  11. #define P system("PAUSE");
  12. #define H return 0;
  13. #define pb push_back
  14. using namespace std;
  15. const long long A=100000000000000LL,N=1228228;
  16.  
  17. long long mask,i,j,n,m,k,a[N],b[N],x,y,z,c[21][21],o,ot,dp[N][21];
  18.  
  19. long long len(long long mask){
  20. long long k=0;
  21. for(i=0;i<n;i++)if(mask&b[i])k++;
  22. return k;
  23. }
  24.  
  25. int main(){
  26. cin>>n>>m>>k;
  27. for(i=0;i<n;i++)scanf("%d",&a[i]);
  28. b[0]=1;
  29. for(i=1;i<=n;i++)b[i]=b[i-1]*2;
  30. while(k--)scanf("%d%d%d",&x,&y,&z),c[x-1][y-1]=z;
  31. for(i=0;i<n;i++)dp[b[i]][i]=a[i];
  32. for(mask=0;mask<b[n];mask++)for(i=0;i<n;i++)if(mask&b[i]){
  33. for(j=0;j<n;j++)if((mask&b[j])==0)dp[(mask|b[j])][j]=max(dp[(mask|b[j])][j],dp[mask][i]+c[i][j]+a[j]);
  34. }
  35. for(mask=0;mask<b[n];mask++)if(len(mask)==m)for(i=0;i<n;i++)o=max(o,dp[mask][i]);
  36. cout<<o<<"\n";
  37. }
Success #stdin #stdout 0s 224128KB
stdin
Standard input is empty
stdout
0