Submission #991925

#	Time	Username	Problem	Language	Result	Execution time	Memory
991925		KK_1729	Gym Badges (NOI22_gymbadges)	C++17	15 / 100	438 ms	1048576 KiB

Main

#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 = {{}};
    FOR(i,0,n) o.pb({x[i], l[i]});
    sort(all(o), comp);
    
    vector<vector<int>> dp(n+1, vector<int>(n+1, 1e15));
    dp[0][0] = 0;
    FOR(i,1,n+1){
        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][j], dp[i-1][j-1]+o[i].first);
        }
    }
    int ans = 0;
    FOR(i,1,n+1){
        if (dp[n][i] < 1e14) 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();
}

• Subtask 1: 15 / 15
• Subtask 2: 0 / 9
• Subtask 3: 0 / 27
• Subtask 4: 0 / 49