fork download
copy 
  1. /*
  2.     AUTHOR:hruday pabbisetty
  3.     NIT ROURKElA
  4. */
  5. #include <bits/stdc++.h>
  6. #include <tr1/unordered_map>
  7. using namespace std;
  8. using namespace std::tr1;
  9. #define opt ios_base::sync_with_stdio(0)
  10. #define lli long long int
  11. #define ulli unsigned long long int
  12. #define I int
  13. #define S string
  14. #define D double
  15. #define rep(i,a,b) for(i=a;i<b;i++)
  16. #define repr(i,a,b) for(i=a;i>b;i--)
  17. #define in(n) scanf("%lld",&n)
  18. #define in2(a,b) scanf("%lld %lld",&a,&b)
  19. #define in3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
  20. #define out(n) printf("%lld\n",n)
  21. #define inu(a) scanf("%lld",&a)
  22. #define outu(a) printf("%llu",a)
  23. #define ins(s) scanf("%s",&s)
  24. #define outs(s) printf("%s",s)
  25. #define mod 1000000007
  26. #define inf 100000000000000
  27. typedef long long       ll;
  28. typedef pair<lli,lli>  plli;
  29. typedef vector<lli>     vlli;
  30. typedef vector<ulli>    vulli;
  31. typedef vector<ll>      vll;
  32. typedef vector<string>  vs;
  33. typedef vector<plli>     vplli;
  34. #define MM(a,x)  memset(a,x,sizeof(a));
  35. #define ALL(x)   (x).begin(), (x).end()
  36. #define P(x)       cerr<<"{"#x<<" = "<<(x)<<"}"<<endl;
  37. #define P2(x,y)       cerr<<"{"#x" = "<<(x)<<", "#y" = "<<(y)<<"}"<<endl;
  38. #define P3(x,y,z)  cerr<<"{"#x" = "<<(x)<<", "#y" = "<<(y)<<", "#z" = "<<(z)<<"}"<<endl;
  39. #define P4(x,y,z,w)cerr<<"{"#x" = "<<(x)<<", "#y" = "<<(y)<<", "#z" = "<<(z)<<", "#w" = "<<(w)<<"}"<<endl;
  40. #define PP(x,i)     cerr<<"{"#x"["<<i<<"] = "<<x[i]<<"}"<<endl;
  41. #define TM(a,b)     cerr<<"{"#a" -> "#b": "<<1000*(b-a)/CLOCKS_PER_SEC<<"ms}\n";
  42. #define UN(v)    sort(ALL(v)), v.resize(unique(ALL(v))-v.begin())
  43. #define mp make_pair
  44. #define pb push_back
  45. #define f first
  46. #define s second
  47. #define sz() size()
  48. #define nl cout<<"\n"
  49. #define MX1 100005
  50. #define MX2 1000005
  51. #define bs binary_search
  52. #define lb lower_bound
  53. #define ub upper_bound
  54. lli dx[]={0,0,-1,1};
  55. lli dy[]={1,-1,0,0};
  56. lli power(lli a,lli b)
  57.     {
  58.     lli value;
  59.     if(b==0)
  60.         {
  61.         return 1;
  62.     }
  63.     else if(b%2==0)
  64.         {
  65.         value=power(a,b/2)%mod;
  66.         return(value*value)%mod;
  67.     }
  68.     else
  69.         {
  70.         value=power(a,b/2)%mod;
  71.         return ((a*value)%mod*(value))%mod;
  72.     }
  73. }
  74. lli a[25],n,b[25],dp[(1<<20)+1][2];
  75. lli f(lli pos)
  76. {
  77.     lli i,flag=0;
  78.     rep(i,1,1+n)
  79.     {
  80.         if(!b[i])
  81.         {
  82.             flag=1;
  83.         }
  84.     }
  85.     if(!flag)
  86.     {
  87.         return 0;
  88.     }
  89.     lli sum=0;
  90.     rep(i,1,1+n)
  91.     {
  92.         if(b[i])
  93.         {
  94.             sum+=(1<<i);
  95.         }
  96.     }
  97.     if(dp[sum][pos]!=-1)
  98.     {
  99.         return dp[sum][pos];
  100.     }
  101.     lli ans=inf;
  102.     if(pos==0)
  103.     {
  104.         lli i,j;
  105.         rep(i,1,1+n)
  106.         {
  107.             if (b[i])
  108.             {
  109.                 continue;
  110.             }
  111.             for(int j = i+1; j <= n; ++j)
  112.             {
  113.                 if(!b[j])
  114.                 {
  115.                     b[i]=1;
  116.                     b[j]=1;
  117.                     ans=min(ans,max(a[i],a[j])+f(1));
  118.                     b[i]=0;
  119.                     b[j]=0;
  120.                 }
  121.             }
  122.         }
  123.         return dp[sum][pos]=ans;
  124.     }
  125.     else
  126.     {
  127.         lli i,ans=inf;
  128.         rep(i,1,1+n)
  129.         {
  130.             if(b[i])
  131.             {
  132.                 b[i]=0;
  133.                 ans=min(ans,a[i]+f(0));
  134.                 b[i]=1;
  135.             }
  136.         }
  137.         return dp[sum][pos]=ans;
  138.     }
  139.     return inf;
  140. }
  141. int main()
  142. {
  143.       /*  #ifndef ONLINE_JUDGE
  144.         freopen("input.txt","r",stdin);
  145.         freopen("output.txt","w",stdout);
  146.         #endif*/
  147.     opt;
  148.     lli t;
  149.     cin>>t;
  150.     while(t--)
  151.     {
  152.         lli i,j;
  153.         cin>>n;
  154.         rep(i,0,power(2,n+1))
  155.         {
  156.             dp[i][0]=-1;
  157.             dp[i][1]=-1;
  158.         }
  159.         rep(i,1,1+n)
  160.         {
  161.             b[i]=0;
  162.             cin>>a[i];
  163.         }
  164.         if(n==1)
  165.         {
  166.             cout<<a[1]<<endl;
  167.             continue;
  168.         }
  169.         cout<<f(0)<<endl;
  170.     }
  171. }
Success #stdin #stdout 0s 32440KB
comments (?)
stdin
copy 
3
2
200 100
3
100 200 300
4
623 821 145 720
stdout
copy 
200
600
2454
https://ideone.com/UJbC9p
language:
C++14 (gcc 8.3)
created:
6 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!