Submission #2527476

---

Source Code Expand

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <utility>
#include <cmath>
#include <iomanip>
#include <queue>
#include <map>
#include <set>
#include <random>
#include <sstream>
#include <stack>
#include <deque>

using namespace std;

#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vl;

int N, P;
vector<pii> p(100100);
int dp[5500][5500] = {};

int main() {
    cin >> N >> P;
    rep(i,N) {
        int a, b;
        cin >> a >> b;
        p[i] = pii(a, b);
    }
    sort(p.rbegin(), p.rend());
    rep(i,5500) dp[0][i] = p[0].second;
    REP(i,1,N) {
        rep(j,5500) {
            if (j <= P+p[i].first && j >= p[i].first) {
                dp[i][j] = max({dp[i-1][j], dp[i-1][j-p[i].first] + p[i].second});
            } else {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }
    cout << dp[N-1][P] << endl;
    return 0;
}

Submission Info

Judge Result