Submission #439323

#	Time	Username	Problem	Language	Result	Execution time	Memory
439323		Tc14	Jelly Flavours (IOI20_jelly)	C++17	100 / 100	283 ms	152848 KiB

jelly

#include <bits/stdc++.h>
#include "jelly.h"
using namespace std;
#define ve vector
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 1e9 + 10;

int find_maximum_unique(int x, int y, ve<int> A, ve<int> B) {

    int n = (int)A.size();
    ve<ve<int>> DPA(n + 1, ve<int>(x + 1, INF));
    ve<ve<int>> DPB(n + 1, ve<int>(y + 1, INF));
    ve<pii> F(n);

    for (int i = 0; i < n; i++) {
        F[i] = {A[i], B[i]};
    }
    sort(F.begin(), F.end());

    DPA[0][0] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= x; j++) {

            int a = j - F[i - 1].first;
            if (a >= 0) {
                DPA[i][j] = min(DPA[i][j], DPA[i - 1][a]);
            }

            if (DPA[i - 1][j] != INF) {
                int b = DPA[i - 1][j] + F[i - 1].second;
                if (b <= y) {
                    DPA[i][j] = min(DPA[i][j], b);
                }
            }

        }
    }

    DPB[n] = ve<int>(y + 1, 0);
    for (int i = n - 1; i >= 0; i--) {
        for (int j = 0; j <= y; j++) {
            DPB[i][j] = DPB[i + 1][j];
            int b = j - F[i].second;
            if (b >= 0) {
                DPB[i][j] = max(DPB[i][j], DPB[i + 1][b] + 1);
            }
        }
    }

    int ans = 0;
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= x; j++) {
            int b = DPA[i][j];
            if (b != INF) {
                ans = max(ans, i + DPB[i][y - b]);
            }
        }
    }

    return ans;
}

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