제출 #991951

#제출 시각아이디문제언어결과실행 시간메모리
991951KK_1729Gym Badges (NOI22_gymbadges)C++17
42 / 100
435 ms1048580 KiB
#include <bits/stdc++.h>

using namespace std;



#define int long long

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)

#define pb push_back

#define all(a) a.begin(), a.end()



void printVector(vector<int> a){

    for (auto x: a) cout << x << " ";

    cout << endl;

}



bool comp(pair<int, int> x, pair<int, int> y){

    return x.first+x.second < y.first+y.second;

}

void solve(){

    

    int n; cin >> n;

    vector<int> x(n), l(n);

    FOR(i,0,n) cin >> x[i];

    FOR(i,0,n) cin >> l[i];

    

    vector<pair<int, int>> o = {{0, 0}};

    FOR(i,0,n) o.pb({x[i], l[i]});

    sort(all(o), comp);

    

    vector<vector<int>> dp(n+1, vector<int>(n+1, 1e18));

    dp[0][0] = 0;

    FOR(i,1,n+1){
		dp[i][0] = 0;
        FOR(j,1,i+1){

            //dp[i][j] = dp[i-1][j];

            if (dp[i-1][j-1] <= o[i].second) dp[i][j] = min(dp[i-1][j], dp[i-1][j-1]+o[i].first);
            else dp[i][j] = dp[i-1][j];

        }

    }

    int ans = 0;

    FOR(i,1,n+1){

        if (dp[n][i] < 1e17) ans = max(ans, i);

    }

    // printVector(dp[n]);

    cout << ans << endl;

}

int32_t main(){

    ios::sync_with_stdio(false);cin.tie(0);

    int t = 1; // cin >> t;

    while (t--) solve();

}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...