Submission #1218328

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218328		JhoZzel	Gym Badges (NOI22_gymbadges)	C++20	51 / 100	180 ms	204280 KiB

Main

#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;
        });


    bool eq = 1;
    for (int i = 0; i < n; i++) if (a[i].ff != a[0].ff) eq = 0;
    if (eq) {
        ll sa = 0;
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            if (sa > a[0].ff) break;
            sa += a[i].ss;
            cnt++;
        }
        cout << cnt << "\n";
       
        return 0;
    }


    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;
}

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