Language: C++

#include <bits/stdc++.h>

//#define DEBUG

#define INF ll_MAX
#define BEAMMAX 10

typedef long long ll;

using namespace std;
 
int main() {
    ll N, W;
    cin >> N >> W;
    vector<ll> v(N), w(N);
    for(int i=0; i<N; ++i) {
        cin >> v[i] >> w[i];
    }
    if(N <= 30) {
        int s = N/2;
        vector<P> dp(1 << s);
        for(int i=0; i<(1 << s); ++i) {
            ll sw = 0, sv = 0;
            for(int j=0; j<s; ++j) {
                if(i >> j & 1) {
                    sw += w[j];
                    sv += v[j];
                }
            }
            dp[i] = make_pair(sw, sv);
        }
        sort(dp.begin(), dp.end());
        int m = 1;
        for(int i=1; i<1<<s; ++i) {
            if(dp[m-1].second < dp[i].second) {
                dp[m++] = dp[i];
            }
        }
        ll res = 0;
        for(int i=0; i<1<<(N - s); ++i) {
            ll sw = 0, sv = 0;
            for(int j=0; j<N-s; ++j) {
                if(i >> j & 1) {
                    sw += w[j+s];
                    sv += v[j+s];
                }
            }
            if(sw <= W) {
                ll tv = (lower_bound(dp.begin(), dp.begin()+m, make_pair(W-sw, INF)) - 1)->second;
                res = max(res, sv+tv);
            }
        }
        cout << res << endl;
    } else if(*max_element(v.begin(), v.end()) <= 1000) {
        ll V = accumulate(v.begin(), v.end(), 0LL);
        vector<ll> dp(V+1, INF);
        dp[0] = 0;
        for(int i=0; i<N; ++i) {
            for(int j=V-v[i]; j>=0; --j) {
                dp[j+v[i]] = min(dp[j+v[i]], dp[j] + w[i]);
            }
        }
        for(int i=V; i>=0; --i) {
            if(dp[i] <= W) {
                cout << i << endl;
                return 0;
            }
        }
    } else {
        vector<ll> dp(W+1, -1);
        dp[0] = 0;
        for(int i=0; i<N; ++i) {
            for(int j=W-w[i]; j>=0; --j) {
                if(dp[j] == -1) {
                    continue;
                }
                dp[j+w[i]] = max(dp[j+w[i]], dp[j] + v[i]);
            }
        }
        cout << *max_element(dp.begin(), dp.end()) << endl;
    }
}

Compiler output:
a.cc: In function 'int main()':
a.cc:21:16: error: 'P' was not declared in this scope
   21 |         vector<P> dp(1 << s);
      |                ^
a.cc:21:17: error: template argument 1 is invalid
   21 |         vector<P> dp(1 << s);
      |                 ^
a.cc:21:17: error: template argument 2 is invalid
a.cc:30:15: error: invalid types 'int[int]' for array subscript
   30 |             dp[i] = make_pair(sw, sv);
      |               ^
a.cc:32:17: error: request for member 'begin' in 'dp', which is of non-class type 'int'
   32 |         sort(dp.begin(), dp.end());
      |                 ^~~~~
a.cc:32:29: error: request for member 'end' in 'dp', which is of non-class type 'int'
   32 |         sort(dp.begin(), dp.end());
      |                             ^~~
a.cc:35:18: error: invalid types 'int[int]' for array subscript
   35 |             if(dp[m-1].second < dp[i].second) {
      |                  ^
a.cc:35:35: error: invalid types 'int[int]' for array subscript
   35 |             if(dp[m-1].second < dp[i].second) {
      |                                   ^
a.cc:36:19: error: invalid types 'int[int]' for array subscript
   36 |                 dp[m++] = dp[i];
      |                   ^
a.cc:36:29: error: invalid types 'int[int]' for array subscript
   36 |                 dp[m++] = dp[i];
      |                             ^
a.cc:49:41: error: request for member 'begin' in 'dp', which is of non-class type 'int'
   49 |                 ll tv = (lower_bound(dp.begin(), dp.begin()+m, make_pair(W-sw, INF)) - 1)->second;
      |                                         ^~~~~
a.cc:49:53: error: request for member 'begin' in 'dp', which is of non-class type 'int'
   49 |                 ll tv = (lower_bound(dp.begin(), dp.begin()+m, make_pair(W-sw, INF)) - 1)->second;
      |                                                     ^~~~~
a.cc:5:13: error: 'll_MAX' was not declared in this scope
    5 | #define INF ll_MAX
      |             ^~~~~~
a.cc:49:80: note: in expansion of macro 'INF'
   49 |                 ll tv = (lower_bound(dp.begin(), dp.begin()+m, make_pair(W-sw, INF)) - 1)->second;
      |                                                                                ^~~
a.cc:5:13: error: 'll_MAX' was not declared in this scope
    5 | #define INF ll_MAX
      |             ^~~~~~
a.cc:56:28: note: in expansion of macro 'INF'
   56 |         vector<ll> dp(V+1, INF);
      |                            ^~~