Submission #1233018

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233018		maya_s	Jelly Flavours (IOI20_jelly)	C++20	10 / 100	90 ms	156232 KiB

jelly

#include "jelly.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
const ll inf = 1e18;
ll dp[2001][10001];

int find_maximum_unique(int x, int y, vector<int> A, vector<int> B) {
    ll n = A.size();
    vector<pll> v(n);
	for(ll i = 0; i < n; i++) v[i] = {A[i], B[i]};
    sort(v.begin(), v.end());
    vector<ll> a(n), b(n);
    for(ll i = 0; i < n; i++) a[i] = v[i].first, b[i] = v[i].second;
    for(ll i = 0; i < a[0]; i++) dp[0][i] = b[0];
    for(ll i = a[0]; i <= x; i++) dp[0][i] = 0;
    for(ll i = 1; i < n; i++){
        for(ll j = 0; j <= x; j++) {
            dp[i][j] = min(dp[i-1][j] + b[i], (j >= a[i] ? dp[i-1][j - a[i]] : inf));
            // cout << dp[i][j] << " ";
        }
        // cout << "\n";
    }
    ll ans = 0;
    for(ll i = -1; i < n; i++){
        if(i >= 0 && dp[i][x] > y) break;
        priority_queue<ll, vector<ll>, greater<ll>> pq;
        for(ll j = i+1; j < n; j++) pq.push(b[i]);
        ll sum = 0, cnt = 0;
        while(pq.size() && sum + pq.top() <= (i >= 0 ? y - dp[i][x] : y)) sum += pq.top(), pq.pop(), cnt++;
        // cout << sum << " " << cnt << " ";
        ans = max(ans, i+1+cnt);
        // cout << i << " " << ans << "\n";
    }
    return ans;
}

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