Submission #1293244

#TimeUsernameProblemLanguageResultExecution timeMemory
12932441otaGym Badges (NOI22_gymbadges)C++20
0 / 100
825 ms1114112 KiB
#include <bits/stdc++.h>
using namespace std;

#define endl "\n"
#define int long long
#define pii pair<int, int>
#define ff first
#define ss second
#define entire(x) (x).begin(), (x).end()

const int inf = 1e16;

int32_t main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);

    int n; cin >> n;
    vector<pii> 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(entire(a));


    vector<vector<int>> dp(n+1, vector<int>(n+1, inf));
    for (int i = 0; i <= n; i++) dp[i][0] = 0;

    for (int k = 0; k < n; k++){
        auto [lim, gain] = a[k];
        for (int i = 0; i < n; i++){
            dp[k+1][i+1] = dp[k][i+1];
            if (dp[k][i] <= lim) dp[k+1][i+1] = min(dp[k+1][i+1], dp[k][i] + gain);
        }
    }

    int ans = 0;
    for (int i = 1; i <= n; i++){
        if (dp[n][i] >= inf) break;
        ans++;
    }

    cout << ans << endl;

    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...