Submission #1253076

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253076		QwertyPi	Festival (IOI25_festival)	C++20	7 / 100	1094 ms	48196 KiB

festival

#include "festival.h"
#include <bits/stdc++.h>
#define int long long
#define all(a) begin(a), end(a)
using namespace std;

const int MX = 2e14 + 11;

struct coupon {
    int p, t, id;
    bool operator< (const coupon& o) const {
        return p < o.p;
    }
    int apply(int x) {
        return max(-1LL, min(MX, (x - p) * t));
    }
};

vector<coupon> C[5];
int dp[5001][5001][1][1], prv[5001][5001][1][1];

#define forn(i, n) for (int i = 0; i < (int) (n); i++)

vector<int32_t> max_coupons(int32_t A, vector<int32_t> P, vector<int32_t> T) {
    for (int i = 0; i < P.size(); i++) {
        C[T[i]].push_back({P[i], T[i], i});
    }
    for (int t = 1; t <= 4; t++) {
        sort(C[t].begin(), C[t].end());
    }

    forn (c1, C[1].size() + 1) forn (c2, C[2].size() + 1) forn (c3, C[3].size() + 1) forn (c4, C[4].size() + 1)
    {
        dp[c1][c2][c3][c4] = -1;
    }
    dp[0][0][0][0] = A;
    
    forn (c1, C[1].size() + 1) forn (c2, C[2].size() + 1) forn (c3, C[3].size() + 1) forn (c4, C[4].size() + 1)
    {
        int& cur_val = dp[c1][c2][c3][c4];
        int& prv_ptr = prv[c1][c2][c3][c4];
        if (c1 > 0) {
            int new_val = C[1][c1 - 1].apply(dp[c1 - 1][c2][c3][c4]);
            if (new_val > cur_val) {
                cur_val = new_val;
                prv_ptr = 1;
            }
        }
        if (c2 > 0) {
            int new_val = C[2][c2 - 1].apply(dp[c1][c2 - 1][c3][c4]);
            if (new_val > cur_val) {
                cur_val = new_val;
                prv_ptr = 2;
            }
        }
        if (c3 > 0) {
            int new_val = C[3][c3 - 1].apply(dp[c1][c2][c3 - 1][c4]);
            if (new_val > cur_val) {
                cur_val = new_val;
                prv_ptr = 3;
            }
        }
        if (c4 > 0) {
            int new_val = C[4][c4 - 1].apply(dp[c1][c2][c3][c4 - 1]);
            if (new_val > cur_val) {
                cur_val = new_val;
                prv_ptr = 4;
            }
        }
    }

    vector<int> correct;
    forn (c1, C[1].size() + 1) forn (c2, C[2].size() + 1) forn (c3, C[3].size() + 1) forn (c4, C[4].size() + 1)
    {
        if (dp[c1][c2][c3][c4] >= 0 && c1 + c2 + c3 + c4 >= accumulate(all(correct), 0LL)) {
            correct = {c1, c2, c3, c4};
        }
    }

    // for (auto x : correct) cout << x << ' '; cout << endl;

    vector<int32_t> ans;
    while (accumulate(all(correct), 0LL) > 0) {
        auto& K = correct;
        int p = prv[K[0]][K[1]][K[2]][K[3]];
        ans.push_back(C[p][--K[p - 1]].id);
    }
    reverse(all(ans));
    return ans;
}

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