fork download 
  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. pair < ll , vector < ll > > LUU1[36*36+3] , LUU2[36*36+3];
  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[cc].fir = v ; 
  58.             LUU1[cc++].sec=v1;}
  59.             else {
  60.             	LUU2[cc].fir = v ; 
  61.             	LUU2[cc++].sec=v1;
  62.             }
  63.         }   
  64.         return ; 		
  65.     }
  66.     Try1(i+1 , s , v , v1 , digdihouse);
  67.     if ( s + a[i].w <= w) {
  68.         v1.pb(i) ;
  69.         Try1(i+1,s+a[i].w,v+a[i].v , v1 , digdihouse); 
  70.     }
  71. }
  72. bool cmp (pair < ll , vector < ll > > a , pair < ll , vector < ll > > b) {
  73. 	return a.fir < b.fir ;
  74. }
  75. int chat ( ll x  ){
  76. 	int l = 1 , r = cc ;
  77. 	int kq = -1 ; 
  78. 	while ( l <= r ){
  79. 		int m = ( l + r ) >> 1 ;
  80. 		if ( LUU2[m].fir <= x ){
  81.  
  82. 			kq = m , l = m + 1 ;
  83. 		} 
  84. 		else r = m - 1 ;
  85. 	}
  86. 	return kq;
  87. }
  88. void sub2(){
  89. 	vector < ll > v1 ; 
  90.     n1 = n >> 1; 
  91.     Try1( 1 , 0ll , 0ll , v1 , n1 );
  92.     int cc1 = cc ;
  93.     cc1--;
  94.    	cc = 1 , v1.clear() ;
  95.     Try1(n1 + 1 , 0ll , 0ll , v1 , n);
  96.     sort (LUU2 + 1 , LUU2 + cc , cmp) ;
  97.    	cc--;
  98.  
  99.     for (int i = 1 ; i <= cc ; i ++ )
  100.     {
  101.     	if ( LUU2[cc].fir <= w){
  102.     		if (LUU2[i].fir > ans )
  103.     			ans = LUU2[i].fir , k = LUU2[i].sec;
  104.     	}
  105.     }
  106.     for (int i = 1 ; i <= cc1 ; i ++ ){
  107.     	if ( LUU1[cc1].fir <= w){
  108.  
  109.     			if ( LUU1[i].fir > ans  )
  110.     				ans = LUU1[i].fir , k = LUU1[i].sec ;
  111.     		}
  112.     		int VI_TRI_CUA_I = chat ( w - LUU1[i].fir );
  113.     		if (VI_TRI_CUA_I != -1 ){
  114.     		ll haha = LUU2[VI_TRI_CUA_I].fir + LUU1[i].fir ;
  115.     		if ( haha > ans ){
  116.     			ans = haha ;
  117.     			k = LUU2[VI_TRI_CUA_I].sec ;
  118.     			for ( auto x : LUU1[i].sec) k.pb(x) ;
  119.  
  120.     		}
  121.     	}
  122.     }
  123.     sort ( ALL( k)) ;
  124.     cout << k.size() << '\n';
  125.     for ( auto x : k ) cout << x << ' ';
  126. }
  127. void solve(){
  128.     cin >> n >> w ;
  129.     for (int i = 1 ; i <= n ; i ++ )
  130.         cin >> a[i].w >> a[i].v;
  131.     sub2();
  132. }
  133. _nhatminh{
  134. freopen("");
  135. ios_base::sync_with_stdio(0);
  136. cin.tie(0); cout.tie(0);
  137. int q=1;
  138. // cin >> q;
  139. while (q--)
  140.     solve();
  141. cerr << '\n' << "Time elapsed " << TIME << "s.\n";
  142. return (0);
  143. }
  144.  
Success #stdin #stdout #stderr 0.01s 5280KB
comments (?)
stdin 
5 20
7 1
5 8
1 1
7 8
9 7
stdout 
4
1 2 3 4
stderr 
Time elapsed 0.005208s.
https://ideone.com/084ezI
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!