Submission #575452

#	Time	Username	Problem	Language	Result	Execution time	Memory
575452		nghiass001	Jelly Flavours (IOI20_jelly)	C++17	100 / 100	136 ms	156956 KiB

jelly

#include <bits/stdc++.h>
#define FOR(i,l,r) for(int i=(l); i<=(r); ++i)
#define REP(i,l,r) for(int i=(l); i<(r); ++i)
#define FORD(i,r,l) for(int i=(r); i>=(l); --i)
#define REPD(i,r,l) for(int i=(r)-1; i>=(l); --i)
using namespace std;
const int N = 2005, maxM = 10005;
int dp[N][maxM];    /// (i, a) -> min b
int dp2[N][maxM];   /// (i, b) -> max count
pair<int, int> c[N];

int find_maximum_unique(int x, int y, vector<int> a, vector<int> b) {
    int n = a.size();
    FOR(i, 1, n) c[i] = {a[i - 1], b[i - 1]};
    sort(c + 1, c + n + 1);

    FOR(i, 1, n) {
        FOR(j, 0, x) {
            dp[i][j] = dp[i - 1][j] + c[i].second;
            if (j >= c[i].first) dp[i][j] = min(dp[i][j], dp[i - 1][j - c[i].first]);
        }
    }

    FORD(i, n, 1) {
        FOR(j, 0, y) {
            dp2[i][j] = dp2[i + 1][j];
            if (j >= c[i].second) dp2[i][j] = max(dp2[i][j], dp2[i + 1][j - c[i].second] + 1);
        }
    }

    int res = 0;
    FOR(i, 0, n) {
        if (dp[i][x] > y) continue;
        res = max(res, i + dp2[i + 1][y - dp[i][x]]);
    }
    return res;
}

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