fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define ld long double
  4. #define pii pair<int,int>
  5. #define pll pair<ll,ll>
  6. #define plll pair<ll,pll>
  7. #define tull tuple<ll,ll,ll>
  8. #define pb push_back
  9. #define f first
  10. #define endl "\n"
  11. #define se second
  12. #define piii pair<int,pii>
  13. #define id1 id<<1
  14. #define id2 (id<<1)+1
  15. #define MASK(i) (1<<i)
  16. #define TIME "\nTime elapsed : "<<(double)clock()/1000<<" ms"
  17. #define all(x) x.begin(),x.end()
  18. #define fast ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);
  19. using namespace std;
  20. const ll mod = 1e9 + 7;
  21. const ll INF = 1e16;
  22. const ll maxn = 1e6 + 5;
  23. const ll maxs = 1e7;
  24. const ll dx[] = { -1, 0, 0, 1 };
  25. const ll dy[] = { 0, -1, 1, 0 };
  26.  
  27. ll n,k;
  28. ll res = LLONG_MIN;
  29. ll a[maxn],b[maxn];
  30. ll bt[maxn];
  31. vector<ll> ans;
  32.  
  33. void tv()
  34. {
  35.     ans.clear();
  36.  
  37.     for(int i = 1; i <= n; ++i){
  38.         if(bt[i] == 1){
  39.             ans.pb(i);
  40.         }
  41.     }
  42. }
  43.  
  44. void ql(ll i,ll sum,ll w)
  45. {
  46.     if(i == n){
  47.         if(res <= sum){
  48.             res = sum;
  49.             tv();
  50.         }
  51.         return;
  52.     }
  53.  
  54.     if(w + a[i + 1] <= k){
  55.         bt[i + 1] = 1;
  56.         ql(i + 1,sum + b[i + 1],w + a[i + 1]);
  57.     }
  58.     if(w <= k){
  59.         bt[i + 1] = 0;
  60.         ql(i + 1,sum,w);
  61.     }
  62. }
  63.  
  64. int main()
  65. {
  66.     fast
  67.  
  68.     cin >> n >> k;
  69.  
  70.     for(int i = 1; i <= n; ++i){
  71.         cin >> a[i] >> b[i];
  72.     }
  73.  
  74.     ql(0,0,0);
  75.  
  76.     sort(all(ans));
  77.  
  78.     cout << ans.size() << endl;
  79.  
  80.     for(ll i : ans){
  81.         cout << i << ' ';
  82.     }
  83.  
  84.     return 0;
  85. }
  86.  
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/oi6EkG
language:
C++ (gcc 8.3)
created:
30 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!