Submission #2947893

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

int main(){
    int i, j, k;
    int N;
    cin >> N;
    vector<long long> H(N), P(N);
    vector<pair<long long, int>> order(N);
    for(i=0; i<N; i++){
        cin >> H[i] >> P[i];
        order[i] = {H[i]+P[i], i};
    }
    sort(order.begin(), order.end());
    long long dp[5001][5001];
    const long long INF = 1e18;
    for(i=0; i<=N; i++){
        dp[i][0] = 0;
        for(j=1; j<=N; j++) dp[i][j] = INF;
    }
    
    for(i=1; i<=N; i++){
        k = order[i-1].second;
        dp[i][0] = 0;
        for(j=1; j<=i; j++){
            dp[i][j] = dp[i-1][j];
            if(dp[i-1][j-1] <= H[k]) dp[i][j] = min(dp[i][j], dp[i-1][j-1] + P[k]);
        }
    }
    for(i=N; i>=0; i--){
        if(dp[N][i] < INF){
            cout << i << endl;
            return 0;
        }
    }
    return 0;
}

Submission Info

Judge Result