Submission #2525990

---

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;
int a[5100], b[5100];
int dp[5500][5500] = {};

int main() {
    cin >> N >> P;
    rep(i,N) cin >> a[i] >> b[i];
    rep(i,5500) dp[0][i] = b[0];
    REP(i,1,N) {
        rep(j,5500) {
            if (j <= P+a[i] && j >= a[i]) {
                dp[i][j] = max({dp[i-1][j], dp[i-1][j-a[i]] + b[i]});
            } 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