Submission #537759

#	Time	Username	Problem	Language	Result	Execution time	Memory
537759		tabr	Jelly Flavours (IOI20_jelly)	C++17	100 / 100	263 ms	77776 KiB

jelly

#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif

// editorial

int find_maximum_unique(int x, int y, vector<int> a, vector<int> b) {
    int n = (int) a.size();
    vector<pair<int, int>> c(n);
    for (int i = 0; i < n; i++) {
        c[i] = make_pair(a[i], b[i]);
    }
    sort(c.begin(), c.end());
    vector<vector<int>> dp(n + 1, vector<int>(x + 1, -1));
    dp[0][x] = y;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= x; j++) {
            if (dp[i][j] == -1) {
                continue;
            }
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] - c[i].second);
            if (j - c[i].first >= 0) {
                dp[i + 1][j - c[i].first] = max(dp[i + 1][j - c[i].first], dp[i][j]);
            }
        }
    }
    int ans = 0;
    vector<int> d;
    for (int i = n; i >= 0; i--) {
        if (i < n) {
            d.emplace_back(c[i].second);
            sort(d.begin(), d.end());
        }
        vector<int> pref(d.size() + 1);
        for (int j = 0; j < (int) d.size(); j++) {
            pref[j + 1] = pref[j] + d[j];
        }
        for (int j = 0; j <= x; j++) {
            if (dp[i][j] == -1) {
                continue;
            }
            int k = (int) (upper_bound(pref.begin(), pref.end(), dp[i][j]) - pref.begin() - 1);
            ans = max(ans, i + k);
        }
    }
    return ans;
}

#ifdef tabr
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << find_maximum_unique(2, 3, {2, 1, 4}, {2, 3, 2}) << '\n';
    cout << find_maximum_unique(6, 12, {5, 1, 5, 6, 3}, {3, 5, 4, 6, 7}) << '\n';
    return 0;
}
#endif

• Subtask 1: 11 / 11
• Subtask 2: 24 / 24
• Subtask 3: 9 / 9
• Subtask 4: 10 / 10
• Subtask 5: 14 / 14
• Subtask 6: 32 / 32