fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll long long int
  3. using namespace std;
  4. ll couple, ans=0, lll=1;
  5. ll cpl[18][18];
  6. //map<ll, map<string, ll> >mp;
  7. ll mp[17][1<<17];
  8. ll Set(ll N,ll pos){return N=N | (1<<pos);}
  9. ll reset(ll N,ll pos){return N= N & ~(1<<pos);}
  10. bool check(ll N,ll pos){return (bool)(N & (1<<pos));}
  11. ll mrg(ll arr ,ll po, ll cost)
  12. {
  13.     ll skb=0;
  14.     if( mp[po][arr]!=-1 ){
  15.         return mp[po][arr]+cost;
  16.     }
  17.     if(po==couple){
  18.         return cost;
  19.     }
  20.     for(ll i=0; i<couple; i++){
  21.         if(check(arr,i)==0){
  22.             ll tmp_cost = mrg(Set(arr,i) , po+1, cost+cpl[po][i] );
  23.             skb=max(skb, tmp_cost);
  24.         }
  25.     }
  26.     mp[po][arr]=skb-cost;
  27.     return skb;
  28.  
  29. }
  30. int main()
  31. {
  32.     ll t;
  33.     cin>>t;
  34.     for(ll cs=1; cs<=t; cs++)
  35.     {
  36.         cin>>couple;
  37.  
  38.         for(ll i=0; i<couple; i++)
  39.         {
  40.             for(ll j=0; j<couple; j++)
  41.             {
  42.                 cin>>cpl[i][j];
  43.             }
  44.         }
  45.         ll arr=0;
  46.         memset(mp,-1, sizeof mp);
  47.         ans=mrg(arr , 0, 0 );
  48.         cout<<"Case "<<cs<<": "<<ans<<endl;
  49.         ans=0;
  50.  
  51.  
  52.  
  53.     }
  54. }
Success #stdin #stdout 0.01s 20808KB
comments (?)
stdin
copy 
1
2
5 1
7 18
stdout
copy 
Case 1: 23
https://ideone.com/lcbQEM
language:
C++14 (gcc 8.3)
created:
4 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!