Submission #1286626

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286626		kawhiet	Festival (IOI25_festival)	C++20	0 / 100	25 ms	4032 KiB

festival

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

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

pair<int64_t, vector<int>> dp[N][N];

vector<int> max_coupons(int A, vector<int> p, vector<int> t) {
  int n = p.size();
  auto get = [&](vector<int> b) {
    int64_t x = A;
    for (auto i : b) {
      x = (x - p[i]) * t[i];
      if (x < -inf) return -inf;
      if (x > inf) return inf;
    }
    return x;
  };
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      dp[i][j] = {-inf, vector<int>{}};
    }
  }
  if (A >= p[0]) {
    dp[0][1] = {(A - p[0]) * t[0], vector<int>{0}};
  }
  for (int i = 1; i < n; i++) { 
    for (int j = 1; j <= i + 1; j++) {
      dp[i][j] = max(dp[i][j], dp[i - 1][j]);
      if (dp[i - 1][j - 1].second.size() != j - 1) continue;
      vector<int> b = dp[i - 1][j - 1].second;
      int m = b.size();
      b.push_back(i);
      int64_t mx = get(b);
      vector<int> res = b;
      for (int k = m - 1; k >= 0; k--) {
        swap(b[k], b[k + 1]);
        int64_t ret = get(b);
        if (ret > mx) {
          mx = ret;
          res = b;
          assert(get(res) == mx);
        }
      }
      dp[i][j] = max(dp[i][j], {mx, res});
    }
  }
  int mx = 0;
  vector<int> res;
  for (int i = 0; i < n; i++) {
    for (int j = 1; j <= n; j++) {
      auto [k, v] = dp[i][j];
      if (k >= 0 && j > mx) {
        mx = j;
        res = v;
      }
    }
  }
  return res;
}

• 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