fork download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. typedef long long ull;
  5. using namespace std;
  6. vector <ull> A;
  7. vector <ull> dp;
  8. vector <int> ord;
  9. ull calc(ull mask, ull runsum, int n){
  10.     if(dp[mask]==-1){
  11.         for(int i=0; i<n; ++i){
  12.             ull prev=1<<i;
  13.             if(mask&prev){
  14.                 ull prevsum=runsum-A[i];
  15.                 ull prevmask=~mask;
  16.                 prevmask|=prev;
  17.                 prevmask=~prevmask;
  18.                 ull score=calc(prevmask,prevsum,n);
  19.                 score+=prevsum%A[i];
  20.             dp[mask]=max(dp[mask],score);
  21.             }
  22.         }
  23.  
  24.     }
  25.     return dp[mask];
  26. }
  27. int main(){
  28.     int n;
  29.     cin>>n;
  30.     A.resize(n);
  31.     ull tot=0;
  32.     for(int i=0; i<n; ++i){
  33.        ull cur;
  34.        cin>>cur;
  35.        tot+=cur;
  36.        A[i]=cur;
  37.     }
  38.     ull L=1<<(n);
  39.     dp.resize(L);
  40.     for(ull i=1; i<L; ++i)
  41.         dp[i]=-1;
  42.     dp[0]=0;
  43.     ull ans=calc(L-1,tot,n);
  44.     cout<<ans;
  45.     return 0;
  46. }
Success #stdin #stdout 0s 16064KB
comments (?)
stdin
copy 
3
4 8 5
stdout
copy 
6
https://ideone.com/uetc0b
language:
C++ (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!