fork download 
  1. #include<bits/stdc++.h>
  2. typedef long long ll;
  3. typedef unsigned long long ull;
  4. #define str string
  5. #define fi first
  6. #define se second
  7. #define all(x) (x).begin(),(x).end() 
  8. #define pb push_back
  9. #define pii pair<int,int>
  10. #define pll pair<ll,ll>
  11. #define el "\n"
  12. #define foR(i,a,b) for(int i=a;i<=b;i++)
  13. #define FoR(i,b,a) for(int i=b;i>=a;i--)
  14. #define de(n,a) for(int i=1;i<=n;i++) cout<<a[i]<<" ";cout<<el;
  15.  
  16. using namespace std;
  17. const int N = 1e6;
  18. const str NAME = "dttui1";
  19.  
  20. void freop() {
  21.     freopen( (NAME + ".inp" ).c_str(), "r" , stdin );
  22.     freopen( (NAME + ".out" ).c_str(), "w" , stdout );
  23. }
  24.  
  25. pll a[N+2] ;
  26. int n ; 
  27. ll w , res = LLONG_MIN ;
  28. vector < pll > v , vt ;
  29.  
  30. void try1 ( int i , ll s , ll val ) {
  31.     if ( s > w ) return ; 
  32.     if ( i > n/2) {
  33.         v.push_back ( { s , val } ) ;
  34.         return ;
  35.     }
  36.     try1( i + 1 , s , val ) ;
  37.     try1 ( i + 1 , s + a[i].fi , val + a[i].se) ;
  38. }
  39.  
  40. void try2 ( int i , ll s , ll val ) {
  41.     if ( s > w ) return ; 
  42.     if ( i > n ) {
  43.         vt.push_back( { s , val } ) ;
  44.         return ;
  45.     }
  46.     try2 ( i + 1 , s , val ) ;
  47.     try2 ( i + 1 , s + a[i].fi , val + a[i].se ) ;
  48. }
  49.  
  50. int tknp ( ll x ) {
  51.     int k = - 1 ;
  52.     int l = 0 , r = v.size() - 1 ;
  53.     while ( l <= r ) {
  54.         int mid = ( l + r ) >> 1 ;
  55.         if ( v[mid].fi <= x ) {
  56.             k = mid ;
  57.             l = mid + 1 ;
  58.         }
  59.         else r = mid - 1 ;
  60.     }
  61.     return k ;
  62. }
  63.  
  64. void MITM() {
  65.     try1( 1 , 0 , 0 ) ;
  66.     try2 ( n / 2 + 1 , 0 , 0 ) ;
  67.     sort ( all ( v ) ) ;
  68.     for ( int i = 1 ; i < v.size() ; i++ ) {
  69.         v[i].se = max ( v[i].se , v[i-1].se ) ;
  70.     }
  71.     for ( auto x : vt ) {
  72.         int k = tknp( w - x.fi ) ;
  73.         if ( k == -1 ) continue; 
  74.         res = max ( res , x.se + v[k].se ) ; 
  75.     } 
  76.     cout << res ; 
  77. }
  78.  
  79. int main(){
  80.     ios_base::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0) ;
  81.  
  82.     freop() ;
  83.  
  84.     cin >> n >> w ;
  85.     foR(i,1,n) cin >> a[i].fi >> a[i].se ;
  86.  
  87.     MITM() ;
  88.  
  89.     return 0 ;
  90. }
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/iNWb4e
language:
C++ (gcc 8.3)
created:
4 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!