Submission #1337177

#TimeUsernameProblemLanguageResultExecution timeMemory
1337177michael12Gym Badges (NOI22_gymbadges)C++20
42 / 100
636 ms1114112 KiB
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<string>
#include<stack>
#include<queue>
#include<string.h>
#include<array>
#include<algorithm>
#include<cmath>
#define ff first
#define ss second
#define endl '\n'
#define int long long
const int maxn = 5e5;
const int oo = 1e18;
using namespace std;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<pair<int, int>> D(n + 1);

    for(int i = 1; i <= n; i++){
        cin >> D[i].ff;
    }
    for(int i = 1; i <= n; i++){
        cin >> D[i].ss;
    }
    vector<vector<int>> dp(n + 1, vector<int>(n + 1, oo));
    dp[0][0] = 0;
    sort(D.begin() + 1, D.begin() + n + 1, [&](pair<int,int> p1, pair<int,int> p2){
    return (p1.ff + p1.ss) < (p2.ff + p2.ss);
    });
    for(int i = 1; i <= n; i++){
        for(int j = 0; j <= i; j++){
            dp[i][j] = dp[i - 1][j];
            if(j > 0 && dp[i - 1][j - 1] <= D[i].ss){
                dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + D[i].ff);
            }
        }
    }
    int mx = -1;
    for(int i = n; i >= 0; i--){
        if(dp[n][i] != oo){
            mx = max(mx, i);
        }
    }
    cout << mx;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...