Submission #1266061

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266061		SHZhang	축제 (IOI25_festival)	C++20	100 / 100	122 ms	93352 KiB

festival

#include "festival.h"
#include <algorithm>
#include <utility>

using namespace std;

#define ll long long

ll price[200005], type[200005], idx[200005];
const ll INF = 1000000000000000000LL;

ll f[200005][50];
bool use[200005][50];

bool compare(pair<pair<ll, ll>, int> a1, pair<pair<ll, ll>, int> b1)
{
    pair<ll, ll> a = a1.first;
    pair<ll, ll> b = b1.first;
    ll val1 = a.second == 1 ? INF + a.first : (6LL * a.first * a.second) / (a.second - 1);
    ll val2 = b.second == 1 ? INF + b.first : (6LL * b.first * b.second) / (b.second - 1);
    return val1 < val2;
}

vector<int> max_coupons(int A, vector<int> P, vector<int> T) {
    int n = P.size();
    vector<pair<pair<ll, ll>, int>> pairs;
    for (int i = 0; i < n; i++) {
        pairs.push_back(make_pair(make_pair((ll)P[i], (ll)T[i]), i));
    }
    sort(pairs.begin(), pairs.end(), compare);
    for (int i = 0; i < n; i++) {
        price[i] = pairs[i].first.first;
        type[i] = pairs[i].first.second;
        idx[i] = pairs[i].second;
    }
    ll balance = A;
    vector<int> ans;
    int cur = 0;
    while (cur < n) {
        ll nbalance = (balance - price[cur]) * type[cur];
        if (nbalance < balance) break;
        balance = nbalance;
        ans.push_back(idx[cur]);
        if (balance >= INF) {
            for (int j = cur + 1; j < n; j++) {
                ans.push_back(idx[j]);
            }
            return ans;
        }
        cur++;
    }
    if (cur == n) return ans;
    for (int i = cur; i < n; i++) {
        for (int j = 0; j < 50; j++) f[i][j] = -1;
    }
    f[cur][0] = balance;
    f[cur][1] = max((balance - price[cur]) * type[cur], -1LL);
    use[cur][1] = true;
    int endpt = cur + 1;
    while (endpt < n && type[endpt] > 1) endpt++;
    for (int i = cur + 1; i < endpt; i++) {
        for (int j = 0; j < 50; j++) {
            f[i][j] = f[i-1][j];
            if (j > 0) {
                ll f2 = (f[i-1][j-1] - price[i]) * type[i];
                if (f2 > f[i][j]) {
                    use[i][j] = true;
                    f[i][j] = f2;
                }
            }
        }
    }
    int best = 0;
    vector<int> bestextra;
    vector<int> bestdecreases;
    for (int i = 0; i < 50; i++) {
        ll remain = f[endpt-1][i];
        if (remain < 0) continue;
        vector<int> extra;
        for (int j = endpt; j < n; j++) {
            if (price[j] <= remain) {
                remain -= price[j];
                extra.push_back(idx[j]);
            }
        }
        if (extra.size() + i > best) {
            best = extra.size() + i;
            bestextra = extra;
            vector<int> decreases;
            int x = endpt - 1;
            int amt = i;
            while (x >= cur) {
                if (use[x][amt]) {
                    decreases.push_back(idx[x]);
                    amt--;
                }
                x--;
            }
            bestdecreases = decreases;
        }
    }
    reverse(bestdecreases.begin(), bestdecreases.end());
    for (int x: bestdecreases) {
        ans.push_back(x);
    }
    for (int x: bestextra) {
        ans.push_back(x);
    }
    return ans;
}

• 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