Submission #1286814

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286814		kawhiet	Festival (IOI25_festival)	C++20	0 / 100	1103 ms	602084 KiB

festival

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

constexpr int N = 71;
constexpr int64_t inf = 1e15;

int64_t dp[N][N][N][N];
array<int, 4> from[N][N][N][N];

vector<int> max_coupons(int A, vector<int> P, vector<int> T) {
  int n = P.size();
  vector<array<int, 2>> a, b, c, d;
  for (int i = 0; i < n; i++) {
    if (T[i] == 1) {
      a.push_back({P[i], i});
    } else if (T[i] == 2) {
      b.push_back({P[i], i});
    } else if (T[i] == 3) {
      c.push_back({P[i], i});
    } else {
      d.push_back({P[i], i});
    }
  }
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      for (int k = 0; k < N; k++) {
        for (int t = 0; t < N; t++) {
          dp[i][j][k][t] = -inf;
        }
      }
    }
  }
  int n1 = a.size();
  int n2 = b.size();
  int n3 = c.size();
  int n4 = d.size();
  sort(a.begin(), a.end());
  sort(b.begin(), b.end());
  sort(c.begin(), c.end());
  sort(d.begin(), d.end());
  dp[0][0][0][0] = A;
  for (int i = 0; i <= n1; i++) {
    for (int j = 0; j <= n2; j++) {
      for (int k = 0; k <= n3; k++) {
        for (int t = 0; t <= n4; t++) {
          int64_t x = dp[i][j][k][t];
          if (i < n1 && x - a[i][0] > dp[i + 1][j][k][t]) {
            dp[i + 1][j][k][t] = x - a[i][0];
            from[i + 1][j][k][t] = {i, j, k, t};
          }
          if (j < n2 && (x - b[j][0]) * 2 > dp[i][j + 1][k][t]) {
            dp[i][j + 1][k][t] = (x - b[j][0]) * 2;
            from[i][j + 1][k][t] = {i, j, k, t};
          }
          if (k < n3 && (x - c[k][0]) * 3 > dp[i][j][k + 1][t]) {
            dp[i][j][k + 1][t] = (x - c[k][0]) * 3;
            from[i][j][k + 1][t] = {i, j, k, t};
          }
          if (t < n4 && (x - d[t][0]) * 4 > dp[i][j][k][t + 1]) {
            dp[i][j][k][t + 1] = (x - d[t][0]) * 4;
            from[i][j][k][t + 1] = {i, j, k, t};
          }
        }
      }
    }
  }
  int mx = 0;
  array<int, 4> res = {0, 0, 0, 0};
  for (int i = 0; i <= n1; i++) {
    for (int j = 0; j <= n2; j++) {
      for (int k = 0; k <= n3; k++) {
        for (int t = 0; t <= n4; t++) {
          if (dp[i][j][k][t] >= 0 && i + j + k + t > mx) {
            mx = i + j + k + t;
            res = {i, j, k, t};
          }
        }
      }
    }
  }
  auto dbg = [&](array<int, 4> a) {
    cout << a[0] << ' ' << a[1] << ' ' << a[2] << ' ' << a[3] << endl;
  };
  vector<int> ret;
  while (res != array<int, 4>{0, 0, 0, 0}) {
    auto cur = from[res[0]][res[1]][res[2]][res[3]];
    if (res[0] != cur[0]) ret.push_back(a[res[0] - 1][1]);
    if (res[1] != cur[1]) ret.push_back(b[res[1] - 1][1]);
    if (res[2] != cur[2]) ret.push_back(c[res[2] - 1][1]);
    if (res[3] != cur[3]) ret.push_back(d[res[3] - 1][1]);
    res = cur;
  }
  reverse(ret.begin(), ret.end());
  return ret;
}

• 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