Submission #1259326

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259326		Aviansh	Festival (IOI25_festival)	C++20	27 / 100	159 ms	186628 KiB

festival

#include "festival.h"
#include <bits/stdc++.h>

using namespace std;

bool comp(array<long long,3>&a, array<long long,3>&b){
    if(a[0]*a[1]*b[1]+b[0]*b[1]==b[0]*a[1]*b[1]+a[0]*a[1]){
        return a[0]<b[0];
    }
    return a[0]*a[1]*b[1]+b[0]*b[1]<b[0]*a[1]*b[1]+a[0]*a[1];
}

vector<int> max_coupons(int a, vector<int> P, vector<int> T) {
    const long long inf = 1e15;
    long long A = a;
    int n = P.size();
    array<long long,3>arr[n];
    for(int i = 0;i<n;i++){
        arr[i]={P[i],T[i],i};
    }
    sort(arr,arr+n,comp);
    int fir = 0;
    for(int i = 0;i<n;i++){
        if(A<=(A-arr[i][0])*arr[i][1]){
            fir++;
            A-=arr[i][0];
            A*=arr[i][1];
            A=min(A,inf);
        }
        else{
            break;
        }
    }
    vector<int>firp;
    for(int i = 0;i<fir;i++){
        firp.push_back(arr[i][2]);
    }
    const int lg = 75;
    long long dp[n][lg];
    int par[n][lg];
    //j is 1 indexed.
    for(int i = 0;i<n;i++){
        fill(dp[i],dp[i]+lg,-inf);
        fill(par[i],par[i]+lg,-1);
    }
    dp[fir][0]=A;
    dp[fir][1]=(A-arr[fir][0])*arr[fir][1];
    par[fir][1]=fir;
    int onebegin = n;
    for(int i = fir+1;i<n;i++){
        if(arr[i][1]==1){
            onebegin=i;
            break;
        }
        dp[i][0]=dp[i-1][0];
        for(int j = 1;j<lg;j++){
            dp[i][j]=max(dp[i-1][j],(dp[i-1][j-1]-arr[i][0])*arr[i][1]);
            if(dp[i-1][j]>(dp[i-1][j-1]-arr[i][0])*arr[i][1]){
                par[i][j]=par[i-1][j];
            }
            else{
                par[i][j]=i;
            }
            dp[i][j]=min(dp[i][j],inf);
        }
    }
    vector<int>psum;
    for(int i = onebegin;i<n;i++){
        if(psum.size()==0){
            psum.push_back(arr[i][0]);
            continue;
        }
        psum.push_back(psum.back()+arr[i][0]);
    }
    vector<int>ans;
    pair<int,int>mxp = {-1,-1};
    if(psum.size()){
        int c = upper_bound(psum.begin(),psum.end(),A)-psum.begin();
        mxp = {c,c};
    }
    for(int i = 0;i<lg;i++){
        if(psum.size()&&dp[onebegin-1][i]>=0){
            int c = upper_bound(psum.begin(),psum.end(),dp[onebegin-1][i])-psum.begin();
            mxp=max(mxp,{i+c,c});
        }
    }
    int mx = mxp.first-mxp.second;
    int curp = par[onebegin-1][mx];
    while(curp!=-1){
        ans.push_back(arr[curp][2]);
        mx--;
        if(curp==0){
            break;
        }
        curp=par[curp-1][mx];
    }
    reverse(ans.begin(),ans.end());
    for(int i : ans){
        firp.push_back(i);
    }
    for(int i = 0;i<mxp.second;i++){
        firp.push_back(arr[onebegin+i][2]);
    }
    return firp;
}

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