제출 #1314324

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1314324		mikolajsz	Jelly Flavours (IOI20_jelly)	C++20	100 / 100	18 ms	524 KiB

jelly

#include <bits/stdc++.h>
#include "jelly.h"
using namespace std;

// n <= 2000, x,y <= 10000, a_i, b_i <= 10000

static inline int suffix_max_count(const vector<int>& freqA, int budget) {
    int cnt = 0;
    int rem = budget;

    // cost 0: take all free items
    cnt += freqA[0];

    // costs 1..10000
    for (int cost = 1; cost < (int)freqA.size(); ++cost) {
        int c = freqA[cost];
        if (c == 0) continue;
        if (rem < cost) break;

        int take = min(c, rem / cost);
        cnt += take;
        rem -= take * cost;

        if (rem < cost) break;
    }
    return cnt;
}

int find_maximum_unique(int x, int y, std::vector<int> a, std::vector<int> b) {
    int n = (int)a.size();

    // items: (a_i, b_i)
    vector<pair<int,int>> items(n);
    for (int i = 0; i < n; ++i) items[i] = {a[i], b[i]};

    // sort by b ascending
    sort(items.begin(), items.end(), [](const auto& p1, const auto& p2){
        if (p1.second != p2.second) return p1.second < p2.second;
        return p1.first < p2.first;
    });

    const int MAXC = 10000;

    // freqA[c] = how many items in current suffix have a = c
    vector<int> freqA(MAXC + 1, 0);
    for (auto [ai, bi] : items) freqA[ai]++;

    // dp[c] = maximum sum of b we can "cover" using A-cost <= c (subset of prefix)
    vector<int> dp(x + 1, 0);

    long long prefixB = 0; // sum of b in first t items
    int best = 0;

    for (int t = 0; t <= n; ++t) {
        // need to cover excess = max(0, prefixB - y)
        long long excess_ll = prefixB - (long long)y;
        int excess = (excess_ll > 0 ? (int)excess_ll : 0);

        if (dp[x] >= excess) {
            // find minimal c such that dp[c] >= excess
            int c_min = 0;
            while (c_min <= x && dp[c_min] < excess) ++c_min;

            if (c_min <= x) {
                int rem_budget = x - c_min;
                int extra = suffix_max_count(freqA, rem_budget);
                best = max(best, t + extra);
            }
        }

        if (t == n) break;

        // move item t from suffix to prefix
        int ai = items[t].first;
        int bi = items[t].second;
        freqA[ai]--;
        prefixB += bi;

        // update knapsack with (weight=ai, value=bi)
        if (ai == 0) {
            for (int c = 0; c <= x; ++c) dp[c] += bi;
        } else if (ai <= x) {
            for (int c = x; c >= ai; --c) {
                int cand = dp[c - ai] + bi;
                if (cand > dp[c]) dp[c] = cand;
            }
        }
    }

    return best;
}

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