제출 #1255036

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1255036		NemanjaSo2005	축제 (IOI25_festival)	C++20	15 / 100	1096 ms	254648 KiB

festival

#include "festival.h"
#include<bits/stdc++.h>
#define ll long long
#define f first
#define s second
using namespace std;
const int maxn=2e5+5;
vector<pair<ll,int>> koji[5];
const ll inf=1e18;
int n;
ll cur,pok[5],dp[75][75][75][75];
int pret[75][75][75][75];
ll perform(ll x,pair<ll,ll> sta){
   return max(min(inf,(x-sta.f)*sta.s),-inf/10);
}
std::vector<int> max_coupons(int A, std::vector<int> P, std::vector<int> T) {
   n=P.size();
   for(int i=1;i<=4;i++)
      pok[i]=1;
   for(int i=1;i<=4;i++)
      koji[i].push_back({0,0});
   for(int i=0;i<n;i++)
      koji[T[i]].push_back({P[i],i});
   for(int i=1;i<=4;i++)
      sort(koji[i].begin(),koji[i].end());
   for(int a=0;a<koji[1].size();a++)
      for(int b=0;b<koji[2].size();b++)
         for(int c=0;c<koji[3].size();c++)
            for(int d=0;d<koji[4].size();d++)
               dp[a][b][c][d]=-inf;


   dp[0][0][0][0]=A;
   for(int a=0;a<koji[1].size();a++)
      for(int b=0;b<koji[2].size();b++)
         for(int c=0;c<koji[3].size();c++)
            for(int d=0;d<koji[4].size();d++){
               if(a!=0 and dp[a][b][c][d]<perform(dp[a-1][b][c][d],{koji[1][a].first,1})){
                  dp[a][b][c][d]=perform(dp[a-1][b][c][d],{koji[1][a].first,1});
                  pret[a][b][c][d]=1;
               }
               if(b!=0 and dp[a][b][c][d]<perform(dp[a][b-1][c][d],{koji[2][b].first,2})){
                  dp[a][b][c][d]=perform(dp[a][b-1][c][d],{koji[2][b].first,2});
                  pret[a][b][c][d]=2;
               }
               if(c!=0 and dp[a][b][c][d]<perform(dp[a][b][c-1][d],{koji[3][c].first,3})){
                  dp[a][b][c][d]=perform(dp[a][b][c-1][d],{koji[3][c].first,3});
                  pret[a][b][c][d]=3;
               }
               if(d!=0 and dp[a][b][c][d]<perform(dp[a][b][c][d-1],{koji[4][d].first,4})){
                  dp[a][b][c][d]=perform(dp[a][b][c][d-1],{koji[4][d].first,4});
                  pret[a][b][c][d]=4;
               }
            }
   /*for(int c=0;c<koji[3].size();c++)
      for(int d=0;d<koji[4].size();d++){
         cout<<c<<" "<<d<<endl;
         cout<<endl;
         for(int a=0;a<koji[1].size();a++){
            for(int b=0;b<koji[2].size();b++)
               cout<<dp[a][b][c][d]<<" ";
            cout<<endl;
         }
         cout<<endl;
      }*/
   int ra=0,rb=0,rc=0,rd=0;
   for(int a=0;a<koji[1].size();a++)
      for(int b=0;b<koji[2].size();b++)
         for(int c=0;c<koji[3].size();c++)
            for(int d=0;d<koji[4].size();d++){
               if(dp[a][b][c][d]<0)
                  continue;
               if(a+b+c+d>ra+rb+rc+rd){
                  ra=a;
                  rb=b;
                  rc=c;
                  rd=d;
               }
            }
   vector<int> br;
   while(ra>0 or rb>0 or rc>0 or rd>0){
    //  cout<<ra<<" "<<rb<<" "<<rc<<" "<<rd<<endl;
      //cout<<pret[ra][rb][rc][rd]<<endl;
      br.push_back(pret[ra][rb][rc][rd]);
      switch (pret[ra][rb][rc][rd]){
         case 1:
            ra--;
            break;
         case 2:
            rb--;
            break;
         case 3:
            rc--;
            break;
         default:
            rd--;
      }
   }
   reverse(br.begin(),br.end());
   vector<int> R;
   for(int x:br){
      R.push_back(koji[x][pok[x]].second);
      pok[x]++;
   }
   return R;
}

• 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