제출 #1257493

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1257493		waynetuinfor	Festival (IOI25_festival)	C++20	0 / 100	56 ms	5836 KiB

festival

#include "festival.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>

std::vector<int> max_coupons(int A, std::vector<int> P, std::vector<int> T) {
  std::vector<std::vector<int>> coup(4);
  int N = P.size();
  for (int i = 0; i < N; ++i) {
    coup[T[i] - 1].push_back(i);
  }
  for (int i = 0; i < 4; ++i) {
    std::sort(coup[i].begin(), coup[i].end(),
              [&](int x, int y) { return P[x] > P[y]; });
  }
  std::vector<int> ans;
  int64_t total = std::accumulate(P.begin(), P.end(), 0LL);
  int64_t X = A;
  while (true) {
    int j = -1;
    int64_t Z = X;
    // std::cerr << "X = " << X << "\n";
    for (int i = 0; i < 4; ++i) {
      if (coup[i].empty() || X < P[coup[i].back()]) {
        continue;
      }
      int64_t Y = (X - P[coup[i].back()]) * (i + 1);
      // std::cerr << "type " << i + 1 << " Y = " << Y << "\n";
      if (Y > Z) {
        Z = Y;
        j = i;
      }
    }
    if (j == -1) {
      break;
    }
    X = std::min((X - P[coup[j].back()]) * (j + 1), total);
    ans.push_back(coup[j].back());
    coup[j].pop_back();
  }
  std::vector<int> rem;
  for (int i = 0; i < 4; ++i) {
    rem.insert(rem.end(), coup[i].begin(), coup[i].end());
  }
  sort(rem.begin(), rem.end(), [&](int i, int j) {
    return 1LL * P[i] * T[i] * T[j] + P[j] * T[j] <
           1LL * P[j] * T[i] * T[j] + P[i] * T[i];
  });
  for (int i : rem) {
    if (X < P[i])
      continue;
    X -= P[i];
    X *= T[i];
    ans.push_back(i);
  }
  return ans;
}

• 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