Submission #1284438

#	Time	Username	Problem	Language	Result	Execution time	Memory
1284438		Muhammad_Aneeq	Festival (IOI25_festival)	C++20	0 / 100	232 ms	33464 KiB

festival

#include "festival.h"
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define pii pair<ll,ll>
#define ff first
#define ss second
bool com(pii a,pii b)
{
    if (a.ss==b.ss)
        return a.ff<b.ff;
    return (a.ff*a.ss*(b.ss-1))<(b.ff*b.ss*(a.ss-1));
}
vector<int> max_coupons(int a, vector<int> P, vector<int> T) 
{
    map<pair<int,int>,vector<int>>inds;
    int n=P.size();
    ll A=a;
    vector<pii>vals;
    for (int i=0;i<n;i++)
    {
        inds[{P[i],T[i]}].push_back(i);
        vals.push_back({P[i],T[i]});
    }
    sort(begin(vals),end(vals),com);
    reverse(begin(vals),end(vals));
    // exit(-1);
    vector<pii>tk=vals;
    // cerr<<1<<endl;
    // while (vals.size())
    // {
    //     pii z=vals.back();
    //     if ((A-z.ff)*z.ss>=A)
    //     {
    //         tk.push_back(z);
    //         A=(A-z.ff)*z.ss;
    //         A=min(A,(ll)1e18);
    //         vals.pop_back();
    //         continue;
    //     }
    //     break;
    // }
    // // cerr<<2<<endl;
    // vector<ll>pr[5]={};
    // while (vals.size())
    // {
    //     pr[vals.back().ss].push_back(vals.back().ff);
    //     vals.pop_back();
    // }
    // for (int i=2;i<=4;i++)
    // {
    //     ll cur=A;
    //     vector<ll>vld;
    //     sort(begin(pr[i]),end(pr[i]));
    //     for (auto j:pr[i])
    //     {
    //         if (j>cur)
    //             break;
    //         cur=(cur-j)*i;
    //         vld.push_back(j);
    //     }
    //     pr[i]=vld;
    // }
    // int s2=pr[2].size(),s3=pr[3].size(),s4=pr[4].size();
    // s2=min(s2,33);
    // s3=min(s3,33);
    // s4=min(s4,34);
    // ll dp[s2+1][s3+1][s4+1]={};
    // for (int i=0;i<=s2;i++)
    //     for (int j=0;j<=s3;j++)
    //         for  (int k=0;k<=s4;k++)
    //             dp[i][j][k]=-1;
    // vector<ll>pre={0};
    // for (auto i:pr[1])
    //     pre.push_back(pre.back()+i);
    // dp[0][0][0]=A;
    // int mx=0;
    // vector<int>ind={0,0,0};
    // for (int i=0;i<=s2;i++)
    //     for (int j=0;j<=s3;j++)
    //         for  (int k=0;k<=s4;k++)
    //         {
    //             if (i>0)
    //             {
    //                 if (pr[2][i-1]<=dp[i-1][j][k])
    //                     dp[i][j][k]=max(dp[i][j][k],(dp[i-1][j][k]-pr[2][i-1])*2ll);
    //             }
    //             if (j>0)
    //             {
    //                 if (pr[3][j-1]<=dp[i][j-1][k])
    //                     dp[i][j][k]=max(dp[i][j][k],(dp[i][j-1][k]-pr[3][j-1])*3ll);
    //             }
    //             if (k>0)
    //             {
    //                 if (pr[4][k-1]<=dp[i][j][k-1])
    //                     dp[i][j][k]=max(dp[i][j][k],(dp[i][j][k-1]-pr[4][k-1])*4ll);
    //             }
    //             if (dp[i][j][k]>=0)
    //             {
    //                 ll z=upper_bound(begin(pre),end(pre),dp[i][j][k])-begin(pre);
    //                 if (i+j+k+z-1>mx)
    //                 {
    //                     mx=i+j+k+z-1;
    //                     ind={i,j,k};
    //                 }
    //             }
    //         }
    // int i=ind[0],j=ind[1],k=ind[2];
    // int rem=mx-i-j-k;
    // vector<pii>tl;
    // while (max(i,max(j,k))>0)
    // {
    //     if (i>0&&dp[i][j][k]==(dp[i-1][j][k]-pr[2][i-1])*2ll)
    //     {
    //         tl.push_back({pr[2][i-1],2});
    //         i--;
    //     }
    //     if (j>0&&dp[i][j][k]==(dp[i][j-1][k]-pr[3][j-1])*3ll)
    //     {
    //         tl.push_back({pr[3][j-1],3});
    //         j--;
    //     }
    //     if (k>0&&dp[i][j][k]==(dp[i][j][k-1]-pr[4][k-1])*4ll)
    //     {
    //         tl.push_back({pr[4][k-1],4});
    //         k--;
    //     }
    // }
    // reverse(begin(tl),end(tl));
    // for (int l=0;l<rem;l++)
    //     tl.push_back({pr[1][l],1});
    // for (auto i:tl)
    //     tk.push_back(i);
    vector<int>ans;
    for (auto i:tk)
    {
        ans.push_back(inds[i].back());
        inds[i].pop_back();
    }
    return ans;
}

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