Submission #1262065

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262065		garam1732	Festival (IOI25_festival)	C++20	100 / 100	62 ms	12984 KiB

festival

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

#define ff first
#define ss second
#define bl ' '
#define endl '\n'
#define all(v) (v).begin(), (v).end()
#define comp(v) (v).erase(unique(all(v)), (v).end())
#define lbd(v,x) lower_bound(all(v), (x))-(v).begin()
#define ubd(v,x) upper_bound(all(v), (x))-(v).begin()

typedef long long ll;
typedef pair<int, int> pi;
typedef pair<pi, int> pii;
typedef pair<int, pi> ipi;
typedef pair<pi, pi> pipi;
typedef pair<ll, ll> pll;

const int MAXN = 100100*2;
const ll MOD = 1e9+7;
const ll INF = 1e15;

struct Coupon {
    ll p, t, n;

    bool operator < (const Coupon& x) const {
        if((t==1)^(x.t==1)) return x.t==1;
        if(t==1) return p<x.p;
        return p*t*(x.t-1) < x.p*x.t*(t-1);
    }
} arr[MAXN];

vector<int> lst[5];

const int MAXM = 50;
ll dp[MAXM][MAXM][MAXM];
ll sum[MAXN];

vector<int> res, res1;
std::vector<int> max_coupons(int A, std::vector<int> P, std::vector<int> T) {
    int n = P.size();
    for(int i=0; i<n; i++) arr[i] = {P[i],T[i], i};
    sort(arr, arr+n);

    int idx=0; ll cur=A;
    while(idx<n && cur<INF) {
        if((cur-arr[idx].p)*arr[idx].t < cur) break;

        res.push_back(idx);
        cur = arr[idx].t*(cur-arr[idx].p); idx++;
    }

    if(cur>=INF) {
        while(idx<n) res.push_back(idx++);
        for(auto &x:res) x=arr[x].n;
        return res;
    }

    for(int t=1;t<=4;t++) lst[t] = {-1};
    for(int i=idx;i<n;i++) {
        lst[arr[i].t].push_back(i);
    }

    int sz=lst[1].size();
    for(int i=1; i<sz; i++) sum[i]=sum[i-1]+arr[lst[1][i]].p;

    memset(dp, -1, sizeof dp);
    pair<int, vector<int> > mx = make_pair(0, vector<int>{0});
    for(int i=0;i<MAXM&&i<lst[2].size();i++) {
        for(int j=0;j<MAXM&&j<lst[3].size();j++) {
            for(int k=0;k<MAXM&&k<lst[4].size();k++) {
                if(!i && !j && !k) {
                    dp[i][j][k] = cur;
                } else {
                    int x = max(max(lst[2][i], lst[3][j]), lst[4][k]);
                    int di = (lst[2][i]==x), dj = (lst[3][j]==x), dk = (lst[4][k]==x);
                    if(dp[i-di][j-dj][k-dk] >= arr[x].p) {
                        dp[i][j][k] = arr[x].t*(dp[i-di][j-dj][k-dk]-arr[x].p);
                    }
                }

                if(dp[i][j][k] != -1) {
                    int it = upper_bound(sum, sum+sz, dp[i][j][k])-sum-1;
                    mx = max(mx, make_pair(i+j+k+it, vector<int>{i,j,k,it}));
                }
            }
        }
    }
    
    vector<int> v=mx.ss;
    for(int t=1;t<=v[0];t++) res.push_back(lst[2][t]);
    for(int t=1;t<=v[1];t++) res.push_back(lst[3][t]);
    for(int t=1;t<=v[2];t++) res.push_back(lst[4][t]);
    for(int t=1;t<=v[3];t++) res.push_back(lst[1][t]);

    sort(all(res));
    for(auto &x:res) x=arr[x].n;
    return res;
}

• 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