제출 #1251874

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1251874		aryan12	축제 (IOI25_festival)	C++20	27 / 100	1161 ms	2162688 KiB

festival

#include "festival.h"
#include <bits/stdc++.h>
using namespace std;

std::vector<int> max_coupons(int A, std::vector<int> P, std::vector<int> T) {
  vector<array<long long, 2> > coupons[5];
  coupons[1].push_back({0LL, 0LL});
  coupons[2].push_back({0LL, 0LL});
  coupons[3].push_back({0LL, 0LL});
  coupons[4].push_back({0LL, 0LL});
  int n = P.size();
  for(int i = 0; i < n; i++) {
    coupons[T[i]].push_back({P[i], i});
  }

  sort(coupons[1].begin(), coupons[1].end());
  sort(coupons[2].begin(), coupons[2].end());
  sort(coupons[3].begin(), coupons[3].end());
  sort(coupons[4].begin(), coupons[4].end());

  long long one_siz = coupons[1].size();
  long long two_siz = coupons[2].size();
  long long three_siz = coupons[3].size();
  long long four_siz = coupons[4].size();

  long long dp[one_siz][two_siz][three_siz][four_siz];
  long long par[one_siz][two_siz][three_siz][four_siz];

  for(long long i = 0; i < one_siz; i++) {
    for(long long j = 0; j < two_siz; j++) {
      for(long long k = 0; k < three_siz; k++) {
        for(long long l = 0; l < four_siz; l++) {
          dp[i][j][k][l] = -1;
          par[i][j][k][l] = -1;
        }
      }
    }
  }

  dp[0][0][0][0] = A;
  for(long long i = 0; i < one_siz; i++) {
    for(long long j = 0; j < two_siz; j++) {
      for(long long k = 0; k < three_siz; k++) {
        for(long long l = 0; l < four_siz; l++) {
          if(i != 0) {
            dp[i][j][k][l] = max(dp[i][j][k][l], (dp[i - 1][j][k][l] - coupons[1][i][0]) * 1LL);
          }
          if(j != 0) {
            dp[i][j][k][l] = max(dp[i][j][k][l], (dp[i][j - 1][k][l] - coupons[2][j][0]) * 2LL);
          }
          if(k != 0) {
            dp[i][j][k][l] = max(dp[i][j][k][l], (dp[i][j][k - 1][l] - coupons[3][k][0]) * 3LL);
          }
          if(l != 0) {
            dp[i][j][k][l] = max(dp[i][j][k][l], (dp[i][j][k][l - 1] - coupons[4][l][0]) * 4LL);
          }

          if(dp[i][j][k][l] == (dp[i - 1][j][k][l] - coupons[1][i][0]) * 1LL) {
            par[i][j][k][l] = 1;
          }
          else if(dp[i][j][k][l] == (dp[i][j - 1][k][l] - coupons[2][j][0]) * 2LL) {
            par[i][j][k][l] = 2;
          }
          else if(dp[i][j][k][l] == (dp[i][j][k - 1][l] - coupons[3][k][0]) * 3LL) {
            par[i][j][k][l] = 3;
          }
          else if(dp[i][j][k][l] == (dp[i][j][k][l - 1] - coupons[4][l][0]) * 4LL) {
            par[i][j][k][l] = 4;
          }

          if(dp[i][j][k][l] > 1'000'000'000'000'000'000LL) {
            dp[i][j][k][l] = 1'000'000'000'000'000'000LL;
          }
        }
      }
    }
  }

  long long ii = 0, jj = 0, kk = 0, ll = 0;
  long long cur_val = A;

  for(long long i = 0; i < one_siz; i++) {
    for(long long j = 0; j < two_siz; j++) {
      for(long long k = 0; k < three_siz; k++) {
        for(long long l = 0; l < four_siz; l++) {
          if(ii + jj + kk + ll < i + j + k + l && dp[i][j][k][l] != -1) {
            ii = i;
            jj = j;
            kk = k;
            ll = l;
            cur_val = dp[i][j][k][l];
          }
          else if(ii + jj + kk + ll == i + j + k + l && dp[i][j][k][l] > cur_val) {
            ii = i;
            jj = j;
            kk = k;
            ll = l;
            cur_val = dp[i][j][k][l];
          }
        }
      }
    }
  }

  vector<int> ans;
  while(ii != 0 || jj != 0 || kk != 0 || ll != 0) {
    if(par[ii][jj][kk][ll] == 1) {
      ans.push_back(coupons[1][ii][1]);
      ii--;
      continue;
    }
    if(par[ii][jj][kk][ll] == 2) {
      ans.push_back(coupons[2][jj][1]);
      jj--;
      continue;
    }
    if(par[ii][jj][kk][ll] == 3) {
      ans.push_back(coupons[3][kk][1]);
      kk--;
      continue;
    }
    if(par[ii][jj][kk][ll] == 4) {
      ans.push_back(coupons[4][ll][1]);
      ll--;
      continue;
    }
  }
  reverse(ans.begin(), ans.end());
  return ans;
}

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