fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. int n;
  5. vector<int>a;
  6. ll dp[(1<<20)+2][11];
  7. ll go(int mask, int round){
  8.    //cout<<mask<<" mask, round "<<round<<endl;
  9.    if(dp[mask][round]!=-1)return dp[mask][round];
  10.    // if(__builtin_popcount(mask)==((1<<n)-1)){
  11.    //    //base case 
  12.    //    return 0;
  13.  
  14.    // }
  15.    if(round==n+1)return 0;
  16.    ll ans=0;
  17.    for(int i=0;i<n;++i){
  18.       for(int j=i+1;j<n;++j){
  19.          if(((mask>>i)&1)==0 && ((mask>>j)&1)==0){
  20.             //ith number and jth number are not touched yet 
  21.             //cout<<i<<" i,j "<<j<<endl;
  22.             int newMask = mask | (1<<i);
  23.             newMask  = newMask | (1<<j);
  24.             ans=max(ans, __gcd(a[i], a[j])*round+ go(newMask, round+1));
  25.          }
  26.       }
  27.    }
  28.    return dp[mask][round]=ans;
  29. }
  30.  
  31. long long solve (int N, vector<int> A) {
  32.    // Write your code here
  33.    n=2*N;
  34.    for(int x:A)a.push_back(x);
  35.    memset(dp, -1, sizeof(dp));
  36.    return go(0,1);
  37.  
  38. }
  39.  
  40. int main() {
  41.  
  42.     ios::sync_with_stdio(0);
  43.     cin.tie(0);
  44.     int N;
  45.     cin >> N;
  46.     vector<int> A(2*N);
  47.     for(int i_A = 0; i_A < 2*N; i_A++)
  48.     {
  49.     	cin >> A[i_A];
  50.     }
  51.  
  52.     long long out_;
  53.     out_ = solve(N, A);
  54.     cout << out_;
  55. }
Success #stdin #stdout 0.05s 93772KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/2Q4I3m
language:
C++14 (gcc 8.3)
created:
3 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!