Submission #1264449

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264449		Tymond	Festival (IOI25_festival)	C++20	48 / 100	155 ms	137384 KiB

festival

#include "festival.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define fi first
#define se second
#define vi vector<int>
#define vll vector<long long>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
mt19937_64 rng64(chrono::high_resolution_clock::now().time_since_epoch().count());
inline int rand(int l,int r){return uniform_int_distribution<int>(l, r)(rng);}
inline ll rand(ll l,ll r){return uniform_int_distribution<ll>(l, r)(rng64);}
#ifdef DEBUG
auto&operator<<(auto&o,pair<auto,auto>p){return o<<"("<<p.first<<", "<<p.second<<")";}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{";int i=0;for(auto e:x)o<<","+!i++<<e;return o<<"}";}
#define debug(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(X)
#else
#define debug(...){}
#endif

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

struct pair_hash{
  size_t operator()(const pair<int,int>&x)const{
    return hash<long long>()(((long long)x.first)^(((long long)x.second)<<32));
  }
};

const int MAXM = 50;
vi P, T;
ll A;
int n;

ll val(ll X, ll p, ll t){
    return (ll)(X - p) * t;
}

bool comp(int x, int y){
    return val(val(A, P[x], T[x]), P[y], T[y]) > val(val(A, P[y], T[y]), P[x], T[x]);
}

vi max_coupons(int Ainit, vi Pinit, vi Tinit){
    A = Ainit;
    P = Pinit;
    T = Tinit;
    n = sz(P);

    vector<pii> ones;
    vi p;
    for(int i = 0; i < n; i++){
        if(T[i] == 1){
            ones.pb(mp(P[i], i));
        }else{
            p.pb(i);
        }
    }
    sort(all(ones));
    sort(all(p), comp);
    n = sz(p);
    // cerr << n << '\n';
    // for(auto ele : p){
    //     cerr << P[ele] << ' ' << T[ele] << '\n';
    // }
    vi ans = {};
    for(int i = 0; i < n; i++){
        if(val(A, P[p[i]], T[p[i]]) >= A){
            ans.pb(p[i]);
            A = val(A, P[p[i]], T[p[i]]);
        }else{
            break;
        }
    }
    //cerr << sz(ans) << ' ' << A << '\n';
    vector<vll> dp(n + 1, vll());
    vector<vi> pre(n + 1, vi());
    dp[sz(ans)].assign(MAXM, -1);
    dp[sz(ans)][0] = A;
    for(int i = sz(ans); i < n; i++){
        dp[i + 1].assign(MAXM, -1);
        pre[i + 1].assign(MAXM, -1);
        dp[i + 1][0] = dp[i][0];
        pre[i + 1][0] = 0;
        for(int j = 1; j < MAXM; j++){
            if(dp[i][j - 1] != -1){
                // if(j == 1){
                //     cerr << dp[i][j - 1] << ' ' << val(dp[i][j - 1], P[p[i]], T[p[i]]) << ' ' << dp[i][j] << '\n';
                // }
                if(val(dp[i][j - 1], P[p[i]], T[p[i]]) >= dp[i][j]){
                    dp[i + 1][j] = val(dp[i][j - 1], P[p[i]], T[p[i]]);
                    pre[i + 1][j] = j - 1;
                }else{
                    dp[i + 1][j] = dp[i][j];
                    pre[i + 1][j] = j;
                }
            }else{
                dp[i + 1][j] = dp[i][j];
                pre[i + 1][j] = j;
            }
        }
    }

    vi best = ans;
    for(int i = 0; i < MAXM; i++){
       // cerr << i << ' ' << dp[n][i] << '\n';
        if(dp[n][i] < 0){
            continue;
        }
        
        vi curr = ans;
        int I = n;
        int J = i;
        vi add = {};
        while(I > sz(ans)){
            if(pre[I][J] != J - 1){
                I--;
            }else{
                add.pb(p[I - 1]);
                J--;
                I--;
            }
        }
        reverse(all(add));
        for(auto ele : add){
            curr.pb(ele);
        }

        A = dp[n][i];
        for(int j = 0; j < sz(ones); j++){
            if(ones[j].fi <= A){
                A = val(A, ones[j].fi, 1);
                curr.pb(ones[j].se);
            }else{
                break;
            }
        }

        if(sz(curr) > sz(best)){
            best = curr;
        }
    }

    return best;
}

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