Submission #1255859

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255859		biank	Festival (IOI25_festival)	C++20	100 / 100	77 ms	8120 KiB

festival

#include "festival.h"
#include <bits/stdc++.h>

using namespace std;

#define forsn(i, s, n) for (int i = int(s); i < int(n); i++)
#define forn(i, n) forsn(i, 0, n)
#define dforsn(i, s, n) for (int i = int(n) - 1; i >= int(s); i--)
#define dforn(i, n) dforsn(i, 0, n)

using vi = vector<int>;
using ll = long long;
using vll = vector<ll>;

#define fst first
#define snd second

#define sz(x) int(x.size())
#define all(x) begin(x), end(x)

#define pb push_back
#define eb emplace_back

const int K = 4;
const int L = 32;
const ll INF = 1e18;

vi max_coupons(int A, vi P, vi T) {
    const int n = sz(T);
    vi order(n);
    iota(all(order), 0);
    sort(all(order), [&](const int &lhs, const int &rhs) {
        if (T[lhs] == T[rhs]) return P[lhs] < P[rhs];
        return (T[rhs] - 1LL) * P[lhs] * T[lhs] <
                (T[lhs] - 1LL) * P[rhs] * T[rhs];
    });
    vi ret;
    ll curr = A;
    vi other, ones;
    vi cnt(K + 1, 0);
    for (int i : order) {
        ll nxt = min((curr - P[i]) * T[i], INF);
        if (nxt >= curr) curr = nxt, ret.pb(i);
        else if (T[i] == 1) ones.pb(i);
        else if (cnt[T[i]] < L) other.pb(i), cnt[T[i]]++;
    }
    const int m = sz(other);
    vector<vll> dp(m + 1, vll(m + 1, -1));
    dp[0][0] = curr;
    forn(i, m) {
        int idx = other[i];
        dp[i + 1] = dp[i];
        forn(j, m) if (dp[i][j] >= P[idx]) {
            dp[i + 1][j + 1] = max(dp[i + 1][j + 1], (dp[i][j] - P[idx]) * T[idx]);
        }
    }
    vll pref = {0LL};
    pref.reserve(sz(ones) + 1);
    for (int i : ones) pref.pb(pref.back() + P[i]);
    auto &maxi = dp[m];
    int best = 0, bestA = 0, bestB = 0;
    forn(a, m + 1) {
        int b = int(upper_bound(all(pref), maxi[a]) - begin(pref) - 1);
        if (maxi[a] > 0 && a + b > best) best = a + b, bestA = a, bestB = b;
    }
    vi ans;
    int j = bestA;
    dforn(i, m) {
        int idx = other[i];
        if (j > 0 && dp[i][j - 1] >= P[idx] &&
            dp[i + 1][j] == (dp[i][j - 1] - P[idx]) * T[idx]) {
            ans.pb(idx), j--;
        }
    }
    reverse(all(ans));
    for (int idx : ans) ret.pb(idx);
    forn(i, bestB) ret.pb(ones[i]);
    return ret;
}

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