제출 #1252496

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1252496		Jakub_Wozniak	축제 (IOI25_festival)	C++20	0 / 100	1096 ms	217308 KiB

festival

#include "festival.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 72;
#define st first
#define nd second
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
vector <pll> t[5];
ll dp[maxn][maxn][maxn][maxn];
const ll oo = (1e+16);


std::vector<int> max_coupons(int A, std::vector<int> P, std::vector<int> T) 
{
  ll rA = A;
  int N = P.size();
  for(int i = 0; i < N ; i++)
  {
    t[T[i]].push_back({P[i],i});
  }
  for(int j = 1 ; j <= 4 ; j++)sort(t[j].begin() , t[j].end());

  for(int i = 0 ; i <= t[1].size() ; i++)
  for(int j = 0 ; j <= t[2].size() ; j++)
  for(int k = 0 ; k <= t[3].size() ; k++)
  for(int l = 0 ; l <= t[4].size() ; l++)
  {
    dp[i][j][k][l] = -1;
  }

  int res = 0 , indi = 0 , indj = 0 , indk = 0 ,indl = 0;
  dp[0][0][0][0] = rA;
  for(int i = 0 ; i <= t[1].size() ; i++)
  {
    for(int j = 0 ; j <= t[2].size() ; j++)
    {
      for(int k = 0 ; k <= t[3].size() ; k++)
      {
        for(int l = 0 ; l <= t[4].size() ; l++)
        {
          if(i != 0)dp[i][j][k][l] = max(dp[i][j][k][l] , (dp[i-1][j][k][l]-t[1][i-1].st)*1);
          if(j != 0)dp[i][j][k][l] = max(dp[i][j][k][l] , (dp[i][j-1][k][l]-t[2][j-1].st)*2);
          if(k != 0)dp[i][j][k][l] = max(dp[i][j][k][l] , (dp[i][j][k-1][l]-t[3][k-1].st)*3);
          if(l != 0)dp[i][j][k][l] = max(dp[i][j][k][l] , (dp[i][j][k][l-1]-t[4][l-1].st)*4);
          dp[i][j][k][l] = min(dp[i][j][k][l] , oo);
        }
      }
    }
  }

  for(int i = 0 ; i <= t[1].size() ; i++)
  {
    for(int j = 0 ; j <= t[2].size() ; j++)
    {
      for(int k = 0 ; k <= t[3].size() ; k++)
      {
        for(int l = 0 ; l <= t[4].size() ; l++)
        {
          if(dp[i][j][k][l] >= 0 && i+j+k+l > res)
          {
            res = i+j+k+l;
            indi = i;
            indj = j;
            indk = k;
            indl = l;
          }
        }
      }
    }
  }


  vector <int> K;
  int i = indi , j = indj , k = indk , l = indl;
  while(i != 0 || j != 0 || k != 0 || l != 0)
  {
    if(i != 0 && dp[i][j][k][l] == min(oo,(dp[i-1][j][k][l]-t[1][i-1].st)*2)) 
    {
      K.push_back(t[1][i-1].nd); i--;
    }
    else if(j != 0 && dp[i][j][k][l] == min(oo,(dp[i][j-1][k][l]-t[2][j-1].st)*2)) 
    {
      K.push_back(t[2][j-1].nd); j--;
    }
    else if(k != 0 && dp[i][j][k][l] == min(oo,(dp[i][j][k-1][l]-t[3][k-1].st)*3)) 
    {
      K.push_back(t[3][k-1].nd); k--;
    }
    else if(l != 0 && dp[i][j][k][l] == min(oo,(dp[i][j][k][l-1]-t[4][l-1].st)*4)) 
    {
      K.push_back(t[4][l-1].nd);
      l--;
    }
    else 
    {
      cerr << "EX\n";
      return {};
    }

  }

  reverse(K.begin() , K.end());

  return {K};
}

• 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