fork download
copy 
  1.  
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. const int N = 20;
  5. int n,mat[N][N],dp[N][(1<<N) +5];
  6.  
  7. int solve(int row, int col, int mask){
  8.     if(dp[row][mask]!=-1 )return dp[row][mask];
  9.     ////////////////////////////////
  10.     if(row==n){
  11.         if(n==1)return mat[row][col];
  12.         for(int i=1; i<=n ;i++) if((mask&(1<<(i-1)))==0)return mat[row][i];
  13.     }
  14.     ////////////////////////////////
  15.     int best = 0,bc=0,pre=0;
  16.     for(int i=1; i<=n; i++){
  17.         if((mask & (1<<(i-1))) == 0){
  18.             pre = best;
  19.             best = max(best, solve(row+1,i,mask | (1<<(i-1))));
  20.         }
  21.     }
  22.     return dp[row][mask]=(best+mat[row][col]);
  23. }
  24. int main() {
  25.     /* Enter your code here. Read input from STDIN. Print output to STDOUT */   
  26.     int t;
  27.     scanf("%d",&t);
  28.     while(t--){
  29.         int i,j;
  30.         memset(dp, -1, sizeof dp);
  31.         scanf("%d",&n);
  32.         for(i=1; i<=n; i++){
  33.             for(j=1; j<=n; j++){
  34.                 scanf("%d",&mat[i][j]);
  35.             }
  36.         }
  37.         int ans = 0,mask;
  38.         for(i=1; i<=n; i++){
  39.             mask = 1<<(i-1);
  40.             ans = max(ans,solve(1,i,mask));
  41.         }
  42.         cout<<ans<<"\n";
  43.     }
  44.     return 0;
  45. }
  46.  
Time limit exceeded #stdin #stdout 5s 97984KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/N2drza
language:
C++ (gcc 8.3)
created:
7 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!