Submission #1259318

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259318		Aviansh	Festival (IOI25_festival)	C++20	15 / 100	169 ms	184272 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) {
    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);
    const int lg = 75;
    long long dp[n][lg];
    int par[n][lg];
    //j is 1 indexed.
    const long long inf = 1e15;
    for(int i = 0;i<n;i++){
        fill(dp[i],dp[i]+lg,-inf);
        fill(par[i],par[i]+lg,-1);
    }
    dp[0][0]=A;
    dp[0][1]=(A-arr[0][0])*arr[0][1];
    par[0][1]=0;
    for(int i = 1;i<n;i++){
        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>ans;
    int mx = 0;
    for(int i = 0;i<lg;i++){
        if(dp[n-1][i]>=0){
            mx=i;
        }
    }
    int curp = par[n-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());
    return ans;
}

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