#1191916 (C++23(gcc16)) No.3764 Graduation Live

• 問題: No.3764 Graduation Live
• ユーザー: ei1333333
• 提出日時: 2026-10-08 00:23:01
• 言語: C++23(gcc16) (gcc 16.1.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 1,269 ms / 2,000 ms
• コード長: 4,036 bytes
• コンパイル時間: 4,226 ms
• コンパイル使用メモリ: 391,544 KB
• 実行使用メモリ: 17,016 KB
• 最終ジャッジ日時: 2026-10-09 20:56:02
• 合計ジャッジ時間: 36,443 ms
• ジャッジサーバーID （参考情報）: judge4_0 / judge3_0

ファイルパターン	結果
sample	AC * 3
other	AC * 45

ソースコード

#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

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

using ll = long long;
using Key = unsigned __int128;
using SignedKey = __int128;
constexpr int BITS = 19;  // N <= 300000.
constexpr int PERSON[6][2] = {{0, -1}, {1, -1}, {2, -1},
                               {0, 1}, {0, 2}, {1, 2}};
constexpr Key STEP[6] = {Key(1) << (BITS * 5), Key(1) << (BITS * 4),
                         Key(1) << (BITS * 3), Key(1) << (BITS * 2),
                         Key(1) << BITS, Key(1)};

struct State {
  Key key = 0;
  ll score = 0;
};

struct Pattern {
  array<int8_t, 6> delta{};
  array<int8_t, 3> used_delta{};
  SignedKey key_delta = 0;
  array<uint8_t, 5> changed{};
  uint8_t changed_size = 0;
};

vector<Pattern> make_patterns() {
  set<array<int8_t, 6>> unique;
  array<int8_t, 6> delta{};
  auto add = [&](auto&& self, int left, int first) -> void {
    if (!left) {
      unique.insert(delta);
      return;
    }
    for (int t = first; t < 6; ++t) {
      ++delta[t];
      self(self, left - 1, t);
      --delta[t];
    }
  };
  auto remove = [&](auto&& self, int left, int first, int to_add) -> void {
    if (!left) {
      add(add, to_add, 0);
      return;
    }
    for (int t = first; t < 6; ++t) {
      --delta[t];
      self(self, left - 1, t, to_add);
      ++delta[t];
    }
  };
  for (int r = 0; r <= 2; ++r) remove(remove, r, 0, r + 1);

  vector<Pattern> patterns;
  patterns.reserve(unique.size());
  for (auto d : unique) {
    Pattern p;
    p.delta = d;
    for (int t = 0; t < 6; ++t) {
      if (!d[t]) continue;
      p.changed[p.changed_size++] = t;
      p.key_delta += SignedKey(STEP[t]) * d[t];
      p.used_delta[PERSON[t][0]] += d[t];
      if (PERSON[t][1] != -1) p.used_delta[PERSON[t][1]] += d[t];
    }
    patterns.push_back(p);
  }
  return patterns;
}

void solve(const vector<Pattern>& patterns) {
  int n;
  array<int, 3> stamina;
  cin >> n >> stamina[0] >> stamina[1] >> stamina[2];
  array<vector<ll>, 6> value;
  for (int i = 0; i < n; ++i) {
    int t;
    ll v;
    cin >> t >> v;
    value[t - 1].push_back(v);
  }
  array<int, 6> sizes;
  array<vector<ll>, 6> prefix;
  for (int t = 0; t < 6; ++t) {
    auto& v = value[t];
    sort(v.rbegin(), v.rend());
    sizes[t] = v.size();
    prefix[t].resize(v.size() + 1);
    for (size_t j = 0; j < v.size(); ++j) prefix[t][j + 1] = prefix[t][j] + v[j];
  }

  array<int, 6> count{};
  array<int, 3> used{};
  State current;
  vector<ll> answer;
  for (int depth = 1; depth <= n; ++depth) {
    State next;
    bool found = false;
    for (const Pattern& p : patterns) {
      bool valid = true;
      for (int i = 0; i < 3; ++i) {
        int x = used[i] + p.used_delta[i];
        if (x < 0 || x > stamina[i]) { valid = false; break; }
      }
      if (!valid) continue;
      ll score = current.score;
      for (int j = 0; j < p.changed_size; ++j) {
        int t = p.changed[j];
        int after = count[t] + p.delta[t];
        if (after < 0 || after > sizes[t]) { valid = false; break; }
        score += prefix[t][after] - prefix[t][count[t]];
      }
      if (!valid) continue;
      Key key = Key(SignedKey(current.key) + p.key_delta);
      if (!found || score > next.score ||
          (score == next.score && key < next.key)) {
        next = {key, score};
        found = true;
      }
    }
    if (!found) break;
    current = next;
    for (int t = 0; t < 6; ++t)
      count[t] = int((current.key >> (BITS * (5 - t))) & ((Key(1) << BITS) - 1));
    used[0] = count[0] + count[3] + count[4];
    used[1] = count[1] + count[3] + count[5];
    used[2] = count[2] + count[4] + count[5];
    answer.push_back(current.score);
  }
  cout << answer.size();
  for (ll x : answer) cout << ' ' << x;
  cout << '\n';
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  const vector<Pattern> patterns = make_patterns();
  int test_cases;
  cin >> test_cases;
  while (test_cases--) solve(patterns);
}