fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define int long long 
  3. #define fi           first 
  4. #define si           second 
  5. #define For(i,a,b)   for (int i = (a), _b =(b); i <= _b; ++i)
  6. #define all(v)       v.begin(), v.end()
  7. #define Unique(v)    v.erase(unique(all(v)), v.end())   
  8. #define MASK(i)      (1LL << (i))
  9. #define bit(i,n)     (((n)>>(i)) & 1)
  10. #define Vii          vector<pair<int,int>>
  11. #define setpr(x)     cout<<setprecision(x)<<fixed
  12. #define Prior        priority_queue< pair<int,int> , Vii, greater<Pair> >
  13. using namespace std;
  14.  
  15. const int Mod = 1E9 + 7;
  16. const long long INF  = 4E18;
  17. const int N = (1 << 20);
  18. int n,W;
  19. pair<int,int> dp[N];
  20. pair<int,int> Min(pair<int,int> a, pair<int,int> b, int w)
  21. {   
  22.   //  cout << b.si <<' ' << w << endl;
  23.     if (b.si + w > W)
  24.     {
  25.         b.si = w;
  26.         b.fi += 1;
  27.     }
  28.     else b.si += w;
  29.     return min(a,b);
  30. }
  31. int a[N];
  32. signed main(){
  33.     cin >> n >> W;
  34.     For(i,0,n-1) cin >> a[i];
  35.     For(Mask,1,(1<<n)-1) dp[Mask] = {1e18,1e18};
  36.     dp[0] = {1,0};
  37.     For(Mask,0,(1<<n)-1)
  38.     {
  39.         For(i,0,n-1)
  40.         {
  41.             if(Mask &(1<<i)) {
  42.                 dp[Mask] = Min(dp[Mask],dp[Mask^(1<<i)],a[i]);
  43.             }
  44.         }
  45.     }                           
  46.     cout << dp[(1<<n)-1].fi;
  47. }
  48.  
Success #stdin #stdout 0.01s 5556KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/yJ7ms9
language:
C++14 (gcc 8.3)
created:
9 days 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!