제출 #1280193

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1280193		Muhammad_Aneeq	축제 (IOI25_festival)	C++20	100 / 100	260 ms	34732 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;
    // 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: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 12 / 12
• Subtask 4: 15 / 15
• Subtask 5: 27 / 27
• Subtask 6: 16 / 16
• Subtask 7: 18 / 18