Submission #1218323

#TimeUsernameProblemLanguageResultExecution timeMemory
1218323JhoZzelGym Badges (NOI22_gymbadges)C++20
42 / 100
172 ms204268 KiB
#include <bits/stdc++.h>
using namespace std;

#define ff first
#define ss second

using ll = long long;

const ll INF = 1e16;

const int N = 5000 + 5;

ll dp[N][N];

int main() {
    cin.tie(0) -> sync_with_stdio(0);

    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            dp[i][j] = INF;

    int n; cin >> n;
    vector<pair<int,int>> a(n);
    for (int i = 0; i < n; i++) cin >> a[i].ss;
    for (int i = 0; i < n; i++) cin >> a[i].ff;
    
    sort(a.begin(), a.end(), [&](pair<int,int> x, pair<int,int> y) {
            return x.ff + x.ss < y.ff + y.ss;
        });

    a.insert(a.begin(), pair{0, 0});
    
    for (int i = 0; i <= n; i++) dp[i][0] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            dp[i][j] = dp[i - 1][j];
            if (dp[i - 1][j - 1] <= a[i].ff) {
                dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + a[i].ss);
            }
        }
    }

    int ans = 0;
    for (int j = 1; j <= n; j++) {
        if (dp[n][j] != INF) ans = j;
    }
    cout << ans << "\n";

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...