Submission #3769359

---

Source Code Expand

#include <bits/stdc++.h>
#define MOD 1000000007
// #define MOD 998244353
#define pb push_back
#define ll long long
#define ld long double
#define ft first
#define sd second
using namespace std;

const int N = 5000 + 9;
pair<ll, ll> a[N];
ll dp[N][N];

signed main() {

    // freopen("out.txt","w",stdout);
    ios::sync_with_stdio(false); cin.tie(0);
    int n; cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> a[i].ft >> a[i].sd;
    }
    sort(a + 1, a + n + 1, [&](auto l, auto r) {
        return l.ft + l.sd < r.ft + r.sd;
    });
    dp[1][1] = a[1].sd;
    for(int i = 2; i <= n; i++) {
        dp[i][1] = min(dp[i-1][1], a[i].sd);
        for(int j = 2; j <= i; j++) {
            dp[i][j] = dp[i-1][j] > 0 ? dp[i-1][j] : (ll)1e14;
            if(dp[i-1][j-1] <= a[i].ft) {
                dp[i][j] = min(dp[i][j], dp[i-1][j-1] + a[i].sd);
            }
        }

    }
    // cout << dp[2][2] << endl;
    for(int j = n; j > 0; j--) {
        if(dp[n][j] != 0 && dp[n][j] < 1e11) {
            cout << j << endl;
            return 0;
        }
    }

    return 0;
}

Submission Info

Judge Result