Submission #697735

#	Time	Username	Problem	Language	Result	Execution time	Memory
697735		tvladm2009	Jelly Flavours (IOI20_jelly)	C++17	100 / 100	124 ms	78668 KiB

jelly

#include <bits/stdc++.h>
#include "jelly.h"
 
using namespace std;
 
typedef long long ll;
 
const int N_MAX = 2000;
const int X_MAX = 10000;
 
struct Jelly {
    int a;
    int b;
};
 
Jelly c[N_MAX + 2];
 
int dp[N_MAX + 2][X_MAX + 2];
 
bool operator < (const Jelly &a, const Jelly &b) {
    return make_pair(a.a, a.b) < make_pair(b.a, b.b);
}
 
int find_maximum_unique (int x, int y, vector <int> a, vector <int> b) {
    int n = a.size();
    for (int i = 1; i <= n; i++) {
        c[i] = Jelly{a[i - 1], b[i - 1]};
    }
    sort(c + 1, c + n + 1);
    int answer = 0;
    for (int i = 1; i <= n; i++) {
        int rem = INT_MAX;
        for (int j = 0; j <= x; j++) {
            dp[i][j] = dp[i - 1][j] + c[i].b;
            if (j >= c[i].a) {
                dp[i][j] = min(dp[i][j], dp[i - 1][j - c[i].a]);
            }
            rem = min(rem, dp[i][j]);
        }
        rem = y - rem;
        if (rem < 0) {
            continue;
        }
        vector <int> aux;
        for (int j = i + 1; j <= n; j++) {
            aux.push_back(c[j].b);
        }
        sort(aux.begin(), aux.end());
        int cnt = i;
        for (int it : aux) {
            if (it <= rem) {
                rem -= it;
                cnt++;
            }
        }
        answer = max(answer, cnt);
    }
    return answer;
}

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