Submission #1310340

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310340		beluga_cat	Festival (IOI25_festival)	C++20	0 / 100	1175 ms	2162688 KiB

festival

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

vector<int> max_coupons(int A, vector<int> P, vector<int> T) {
    int N = P.size();

    // BFS state: current tokens + bitmask of used coupons (we'll optimize later)
    struct State {
        long long tokens;
        vector<int> seq;
        vector<bool> used;
    };

    queue<State> q;
    unordered_map<long long, int> best; // tokens -> max coupons

    vector<bool> used(N, false);
    q.push({A, {}, used});
    best[A] = 0;

    vector<int> answer;

    while (!q.empty()) {
        State cur = q.front(); q.pop();

        if ((int)cur.seq.size() > (int)answer.size())
            answer = cur.seq;

        for (int i = 0; i < N; i++) {
            if (cur.used[i]) continue;
            if (cur.tokens < P[i]) continue;

            long long new_tokens = (cur.tokens - P[i]) * T[i];

            // prune worse states
            if (best.count(new_tokens) && best[new_tokens] >= (int)cur.seq.size() + 1)
                continue;

            best[new_tokens] = cur.seq.size() + 1;
            State nxt = cur;
            nxt.tokens = new_tokens;
            nxt.used[i] = true;
            nxt.seq.push_back(i);
            q.push(nxt);
        }
    }

    return answer;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 12
• Subtask 4: 0 / 15
• Subtask 5: 0 / 27
• Subtask 6: 0 / 16
• Subtask 7: 0 / 18