Submission #1253193

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253193		QwertyPi	Festival (IOI25_festival)	C++20	21 / 100	57 ms	21160 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];

#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());
    }

    vector<int> ps {0};
    for (int i = 0; i < C[1].size(); i++) {
        ps.push_back(ps.back() + C[1][i].p);
    }

    C[2].resize(min(30LL, (int) C[2].size()));
    C[3].resize(min(24LL, (int) C[3].size()));
    C[4].resize(min(15LL, (int) C[4].size()));

    vector<coupon> C2;
    for (int t = 1; t <= 4; t++) {
        for (auto c : C[t]) C2.push_back(c);
    }
    sort(all(C2), [] (auto& c1, auto& c2) {
        if (c1.t != c2.t) return (c1.t - 1) * c2.p * c2.t > (c2.t - 1) * c1.p * c1.t;
        return c1.p < c2.p;
    });
    
    vector<int> K {-1};
    for (int c2 = 0; c2 <= min((int) C[2].size(), 30LL); c2++) {
        for (int c3 = 0; c3 <= min((int) C[3].size(), 24LL); c3++) {
            for (int c4 = 0; c4 <= min((int) C[4].size(), 15LL); c4++) {
                int X = A;
                vector<coupon> C3;
                for (int i = 0; i < c2; i++) C3.push_back(C[2][i]);
                for (int i = 0; i < c3; i++) C3.push_back(C[3][i]);
                for (int i = 0; i < c4; i++) C3.push_back(C[4][i]);
                sort(all(C3), [] (auto& c1, auto& c2) {
                    if (c1.t != c2.t) return (c1.t - 1) * c2.p * c2.t > (c2.t - 1) * c1.p * c1.t;
                    return c1.p < c2.p;
                });
                for (auto c : C3) {
                    X = c.apply(X);
                }
                int c1 = upper_bound(all(ps), X) - ps.begin() - 1;
                if (c1 >= 0 && c1 + c2 + c3 + c4 > accumulate(all(K), 0LL))
                    K = {c1, c2, c3, c4};
            }
        }
    }
    vector<int32_t> ans;
    vector<coupon> C3;
    for (int i = 0; i < K[1]; i++) C3.push_back(C[2][i]);
    for (int i = 0; i < K[2]; i++) C3.push_back(C[3][i]);
    for (int i = 0; i < K[3]; i++) C3.push_back(C[4][i]);
    sort(all(C3), [] (auto& c1, auto& c2) {
        if (c1.t != c2.t) return (c1.t - 1) * c2.p * c2.t > (c2.t - 1) * c1.p * c1.t;
        return c1.p < c2.p;
    });
    for (auto c : C3) ans.push_back(c.id);
    for (int i = 0; i < K[0]; i++) {
        ans.push_back(C[1][i].id);
    }
    return ans;
}

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