fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int dp[1<<13][13][13];
  4. int main()
  5. {
  6.     int t,n,*a,*p,i,limit,mask,x,p1,q,r,j;
  7.     cin>>t;
  8.     while(t--)
  9.     {
  10.         cin>>n;
  11.         a = new int[n];
  12.         p = new int[n];
  13.         for(i=0;i<n;i++)
  14.             cin>>a[i];
  15.         for(i=0;i<n;i++)
  16.             cin>>p[i];
  17.         limit = (1<<n);
  18.         memset(dp,100,sizeof(dp));
  19.         for(mask=0;mask<limit;mask++)
  20.         {
  21.             x = __builtin_popcount(mask);
  22.             for(p1=0;p1<n;p1++)
  23.             {
  24.                 for(q=0;q<n;q++)
  25.                 {
  26.                     if(x <= 2)
  27.                         dp[mask][p1][q] = 0;
  28.                     else
  29.                     {
  30.                         if(((mask&(1<<p1)) == 0 || (mask&(1<<q)) == 0) || ((mask&(1<<p1)) && (mask&(1<<q)) && p1 == q))
  31.                           dp[mask][p1][q] = 0;
  32.                         else
  33.                         {
  34.                             for(r=0;r<n;r++)
  35.                             {
  36.                                 if(mask&(1<<r) && r!=p1 && r!=q)
  37.                                     dp[mask][r][p1] = min(dp[mask][r][p1],(dp[mask^(1<<r)][p1][q] + (a[r]^a[p1]^a[q])*p[x-1]));
  38.                             }
  39.                         }
  40.                     }
  41.                 }
  42.             }
  43.         }
  44.         int res = INT_MAX;
  45.         for(i=0;i<n;i++)
  46.         {
  47.             for(j=0;j<n;i++)
  48.                 res = min(res,dp[limit-1][i][j]);
  49.         }
  50.         cout<<res;
  51.     }
  52. }
  53.  
Time limit exceeded #stdin #stdout 5s 20648KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/PnCP9i
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

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!