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 <= x ){
  80.         
  81.             kq = m , l = m + 1 ;
  82.         
  83.         } 
  84.         else r = m - 1 ;
  85.     }
  86.     return kq;*/
  87. }
  88. void sub2(){
  89.     vector < ll > v1 ; 
  90.     n1 = n>>1;
  91.     LUU1.pb(make_pair(make_pair(0,0),v1));
  92.     LUU2.pb(make_pair(make_pair(0,0),v1));
  93.  
  94.     Try1( 1 , 0ll , 0ll , v1 , n1 );
  95.     int cc1 = cc ;
  96.     cc1--;
  97.     cc = 1 , v1.clear() ;
  98.     Try1(n1 + 1 , 0ll , 0ll , v1 , n);
  99.     sort (ALL(LUU2), cmp) ;
  100.     cc--; 
  101.  
  102.     for (int i = 1 ; i <= cc ; i ++ )
  103.     {
  104.         if ( LUU2[i].fir.fir <= w){
  105.             if (LUU2[i].fir.sec > ans )
  106.                 ans = LUU2[i].fir.sec , k = LUU2[i].sec;
  107.         }
  108.     }
  109.     for (int i = 1 ; i <= cc1 ; i ++ ){
  110.         if ( LUU1[i].fir.fir <= w){
  111.  
  112.                 if ( LUU1[i].fir.sec > ans  )
  113.                     ans = LUU1[i].fir.sec , k = LUU1[i].sec ;
  114.             }
  115.             /*int VI_TRI_CUA_I = chat ( w - LUU1[i].fir );
  116.             if (VI_TRI_CUA_I != -1 ){
  117.             ll haha = LUU2[VI_TRI_CUA_I].fir + LUU1[i].fir ;
  118.             if ( haha > ans ){
  119.                 ans = haha ;
  120.                 k = LUU2[VI_TRI_CUA_I].sec ;
  121.                 for ( auto x : LUU1[i].sec) k.pb(x) ;
  122.         
  123.             }*/
  124.         for (int j = 1 ; j <= cc ; j ++ ){
  125.             ll haha = LUU2[j].fir.fir + LUU1[i].fir.fir ;
  126.             if ( haha > w) break;
  127.             ll ccccccc = LUU2[j].fir.sec + LUU1[i].fir.sec ;
  128.             if ( ccccccc > ans){
  129.                 ans = ccccccc ;
  130.                 k = LUU2[j].sec ;
  131.                 for ( auto x : LUU1[i].sec) k.pb(x) ;
  132.             }
  133.         }
  134.     }
  135.     sort ( ALL( k)) ;
  136.     cout << k.size() << '\n';
  137.     for ( auto x : k ) cout << x << ' ';
  138. }
  139. void solve(){
  140.     cin >> n >> w ;
  141.     for (int i = 1 ; i <= n ; i ++ )
  142.         cin >> a[i].w >> a[i].v;
  143.    // if ( n == 15) cout << a[15].w << ' ' << a[15].v << '\n';
  144.      sub2();
  145. }
  146. _nhatminh{
  147. freopen("");
  148. ios_base::sync_with_stdio(0);
  149. cin.tie(0); cout.tie(0);
  150. int q=1;
  151. // cin >> q;
  152. while (q--)
  153.     solve();
  154. cerr << '\n' << "Time elapsed " << TIME << "s.\n";
  155. return (0);
  156. }
  157.  
Success #stdin #stdout #stderr 0.01s 5220KB
comments (?)
stdin
copy 
15 3814991876
854780691 8495411
429830325 278284501
751666535 128642401
838631107 893460711
521301707 51566831
297227079 100308517
974908119 609826140
426827916 396206319
318290378 52518929
782365503 686399713
361308645 430935721
480510231 999047386
910785287 728228145
491348433 370818361
648855959 137883395
stdout
copy 
6
4 8 10 11 12 13
stderr
copy 
Time elapsed 0.007221s.
https://ideone.com/mKUTio
language:
C++14 (gcc 8.3)
created:
3 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!