Submission #1283021

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283021		lukasuliashvili	Festival (IOI25_festival)	C++20	Compilation error	0 ms	0 KiB

festival

#include <bits/stdc++.h>
#include "festival.h"
using namespace std;
#define int long long
#define pb push_back
#define rep(i,a,b) for(int i=a;i<b;i++)
const int INF=1e18,MX=2e14,L=71;

vector<int> max_coupons(int AA,vector<int>P,vector<int>T){
    int A=AA;
    vector<array<int,3>> x;
    int n=P.size();
    vector<array<int,2>> y;
    rep(i,0,n){
        if(T[i]!=1)x.pb({P[i],T[i],i});
        else y.pb({P[i],i});
    }
    sort(x.begin(),x.end(),[&](array<int,3>b,array<int,3>c){
        int v1=-(b[0]*b[1]*c[1]+c[0]*c[1]);
        int v2=-(c[0]*c[1]*b[1]+b[0]*b[1]);
        return v1>v2;
    });
    sort(y.begin(),y.end());
    int m=x.size(),k=y.size();
    vector<vector<int>> dp(n+1,vector<int>(L,-INF));
    vector<vector<int>> par(n+1,vector<int>(L,-1));
    int ptr=0;bool bad=false;
    for(auto [p,t,_]:x){
        if((A-p)*t>=A){
            assert(!bad);
            A=(A-p)*t;
            A=min(A,MX);
            ptr++;
        }else bad=true;
    }
    rep(i,0,n+1)dp[i][0]=A;
    for(int i=ptr+1;i<=m;i++){
        auto [p,t,_]=x[i-1];
        rep(j,0,L){
            if(dp[i-1][j]>=0){
                dp[i][j]=dp[i-1][j];
                par[i][j]=0;
            }
        }
        rep(j,0,L-1){
            if(dp[i-1][j]>=p){
                int val=(dp[i-1][j]-p)*t;
                val=min(val,MX);
                if(val>dp[i][j+1]){
                    dp[i][j+1]=val;
                    par[i][j+1]=1;
                }
            }
        }
    }
    vector<int> pre(k+1,0);
    rep(i,1,k+1)pre[i]=pre[i-1]+y[i-1][0];
    int ans=-1,id=-1,ok=-1;
    rep(i,0,L){
        if(dp[m][i]>=0){
            int val=i,l=0,r=k;
            while(l!=r){
                int mid=(l+r+1)/2;
                if(pre[mid]<=dp[m][i])l=mid;
                else r=mid-1;
            }
            val+=l;
            if(val>ans)ans=val,id=i,ok=l;
        }
    }
    vector<int> vec;
    rep(i,0,ok)vec.pb(y[i][1]);
    for(int i=m;i>ptr;i--){
        if(par[i][id]==1){
            id--;
            vec.pb(x[i-1][2]);
        }
    }
    for(int i=ptr-1;i>=0;i--)vec.pb(x[i][2]);
    reverse(vec.begin(),vec.end());
    return vec;
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccGLbS22.o: in function `main':
grader.cpp:(.text.startup+0x22a): undefined reference to `max_coupons(int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status