fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define _nhatminh  int main()
  3. #define ll long long
  4. #define str string
  5. #define fir first
  6. #define sec second
  7. #define ld long double
  8. #define pb push_back
  9. #define MOD 100000009
  10. #define freopen(name) if(fopen(name".INP","r")) {freopen (name".INP","r",stdin); freopen (name".OUT","w",stdout);}
  11. #define ALL(x) (x).begin(),(x).end()
  12. #define piint pair < int , int >
  13. #define piL pair < int , ll>
  14. #define pLL pair < ll , ll >
  15. #define TIME (1.0*clock()/CLOCKS_PER_SEC)
  16. using namespace std;
  17. const int Max_n=36;
  18. struct cc
  19. {
  20.     ll w , v;
  21. };
  22. cc a[Max_n+3] ;
  23. ll x[Max_n+3];
  24. int n ;
  25. ll w ; ll ans = -1e18;
  26. vector < ll > k ;
  27. void Try ( int i ){
  28.     if ( i > n ){
  29.         std::vector<ll> v;
  30.         ll dem = 0 ,res  = 0 ;
  31.         for (int i = 1 ; i <= n ; i ++ ){
  32.             if (x[i]){
  33.                 dem += a[i].w;
  34.                 res += a[i].v;
  35.                 v.pb(i) ;
  36.             }
  37.             if ( dem > w) return ;
  38.         }
  39.         if (res > ans) ans = res , k = v ;
  40.         return;
  41.     }
  42.     for (int j = 0 ; j <= 1 ; j ++ )
  43.         x[i] = j , Try(i+1);
  44. }
  45. vector<pair < pair < ll , ll >  , vector < ll > >> LUU1 , LUU2;
  46. void sub1(){
  47.     Try(1) ;
  48.     cout << k.size() << '\n';
  49.     for ( auto x : k ) cout << x << ' ';
  50. }
  51. int cc = 1 ;
  52. int n1 ;
  53. void Try1( int i , ll s , ll v , vector<ll> v1 , int digdihouse) {
  54.     if ( i > digdihouse ){
  55.         if ( s <= w && v != 0 ) {
  56.             if ( digdihouse == n1){
  57.                 LUU1.pb(make_pair(make_pair(s,v),v1));
  58.             cc++;}
  59.             else {
  60.                 LUU2.pb(make_pair(make_pair(s,v),v1)); cc++;
  61.             }
  62.         }
  63.         return ;
  64.     }
  65.     Try1(i+1 , s , v , v1 , digdihouse);
  66.     if ( s + a[i].w <= w) {
  67.         v1.pb(i) ;
  68.         Try1(i+1,s+a[i].w,v+a[i].v , v1 , digdihouse);
  69.     }
  70. }
  71. bool cmp (pair < pair < ll , ll >  , vector < ll > > a ,pair < pair < ll , ll >  , vector < ll > > b) {
  72.     return a.fir.fir < b.fir.fir ;
  73. }
  74. int chat ( ll x  ){
  75.     int l = 1 , r = cc ;
  76.     int kq = -1 ;
  77.     while ( l <= r ){
  78.         int m = ( l + r ) >> 1 ;
  79.         if ( LUU2[m].fir.fir <= x ){
  80.  
  81.             kq = m , l = m + 1 ;
  82.  
  83.         }
  84.         else r = m - 1 ;
  85.     }
  86.     return kq;
  87. }
  88. pair < ll , vector <ll >> S[262144+5] ;
  89. void sub2(){
  90.     vector < ll > v1 ;
  91.     n1 = n>>1;
  92.     LUU1.pb(make_pair(make_pair(0,0),v1));
  93.     LUU2.pb(make_pair(make_pair(0,0),v1));
  94.  
  95.     Try1( 1 , 0ll , 0ll , v1 , n1 );
  96.     int cc1 = cc ;
  97.     cc1--;
  98.     cc = 1 , v1.clear() ;
  99.     Try1(n1 + 1 , 0ll , 0ll , v1 , n);
  100.     sort (ALL(LUU2), cmp) ;
  101.     cc--;
  102.  
  103.     for (int i = 1 ; i <= cc ; i ++ )
  104.     {
  105.         if ( LUU2[i].fir.fir <= w){
  106.             if (LUU2[i].fir.sec > ans )
  107.                 ans = LUU2[i].fir.sec , k = LUU2[i].sec;
  108.         }
  109.         S[i].fir = S[i-1].fir;
  110.         S[i].sec=S[i-1].sec;
  111.          if ( LUU2[i].fir.sec > S[i-1].fir )S[i].fir = LUU2[i].fir.sec,S[i].sec=LUU2[i].sec;
  112.     }
  113.     for (int i = 1 ; i <= cc1 ; i ++ ){
  114.         if ( LUU1[i].fir.fir <= w){
  115.  
  116.                 if ( LUU1[i].fir.sec > ans  )
  117.                     ans = LUU1[i].fir.sec , k = LUU1[i].sec ;
  118.             }
  119.             int VI_TRI_CUA_I = chat ( w - LUU1[i].fir.fir );
  120.             if (VI_TRI_CUA_I != -1 ){
  121.             ll haha = S[VI_TRI_CUA_I].fir + LUU1[i].fir.sec ;
  122.             if ( haha > ans ){
  123.                 ans = haha ;
  124.                 k = S[VI_TRI_CUA_I].sec ;
  125.                 for ( auto x : LUU1[i].sec) k.pb(x) ;
  126.  
  127.             }
  128.         }
  129. //        for (int j = 1 ; j <= cc ; j ++ ){
  130. //            ll haha = LUU2[j].fir.fir + LUU1[i].fir.fir ;
  131. //            if ( haha > w) break;
  132. //            ll ccccccc = LUU2[j].fir.sec + LUU1[i].fir.sec ;
  133. //            if ( ccccccc > ans){
  134. //                ans = ccccccc ;
  135. //                k = LUU2[j].sec ;
  136. //                for ( auto x : LUU1[i].sec) k.pb(x) ;
  137. //            }
  138. //        }
  139.     }
  140.     sort ( ALL( k)) ;
  141.     cout << k.size() << '\n';
  142.     for ( auto x : k ) cout << x << ' ';
  143. }
  144. void solve(){
  145.     cin >> n >> w ;
  146.     for (int i = 1 ; i <= n ; i ++ )
  147.         cin >> a[i].w >> a[i].v;
  148.    // if ( n == 15) cout << a[15].w << ' ' << a[15].v << '\n';
  149.      sub2();
  150.    //cout << ans << ' ';
  151. }
  152. _nhatminh{
  153. freopen("");
  154. ios_base::sync_with_stdio(0);
  155. cin.tie(0); cout.tie(0);
  156. int q=1;
  157. // cin >> q;
  158. while (q--)
  159.     solve();
  160. cerr << '\n' << "Time elapsed " << TIME << "s.\n";
  161. return (0);
  162. }
  163.  
Success #stdin #stdout #stderr 0.01s 11900KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
stderr
copy 
Time elapsed 0.005301s.
https://ideone.com/BJxIIQ
language:
C++14 (gcc 8.3)
created:
3 hours 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!