제출 #1021219

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1021219		erray	Cookies (JOI23_cookies)	C++17	100 / 100	110 ms	28752 KiB

cookies

// author: erray
#include <bits/stdc++.h>

#ifdef DEBUG
  #include "debug.h"
#else
  #define debug(...) void(37)
#endif

using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int N;
  cin >> N;
  vector<int> A(N);
  for (int i = 0; i < N; ++i) {
    cin >> A[i];
  }
  auto a = A;    
  sort(a.begin(), a.end());
  int M;
  cin >> M;
  vector<int> B(M);
  for (int i = 0; i < M; ++i) {
    cin >> B[M - i - 1];
  }
  constexpr int SUM = 15000 + 1;
  vector<int> allowed(SUM);
  allowed[0] = -1;
  {
    int64_t sum = 0;
    int p = 0;
    for (int i = 1; i < SUM; ++i) {
      while (p < N && a[p] < i) {
        sum += a[p];
        ++p;
      }
      allowed[i] = sum + (N - p) * i;
    }
  }
  using bs = bitset<SUM>;
  bs one = ~bs{};
  vector<bs> reach(SUM);
  reach[0][0] = true;
  for (auto add : B) { 
    for (int c = 1; c <= (SUM - 1) / add; ++c) {
      reach[c] |= reach[c - 1] << add;
      reach[c] &= one >> max(0, SUM - 1 - allowed[c]);
    } 
  }
  int size = 0;
  int sum = accumulate(a.begin(), a.end(), 0);
  while (size < SUM && !reach[size][sum]) ++size;
  if (size == SUM) {
    cout << -1 << '\n';
    return 0;
  }
  debug(size);
  vector<int> sizes;
  reverse(B.begin(), B.end());
  for (auto x : B) {
    while (size > 0 && reach[size - 1][sum - x]) {
      sum -= x;
      size -= 1;
      sizes.push_back(x);
    }
  }
  //sort(sizes.rbegin(), sizes.rend());  
  reverse(sizes.begin(), sizes.end());
  debug(sizes);
  priority_queue<array<int, 2>> pq;
  for (int i = 0; i < N; ++i) {
    pq.push({A[i], i});
  }
  cout << int(sizes.size()) << '\n';
  for (auto s : sizes) {
    cout << s << ' ';
    vector<array<int, 2>> temp;
    for (int j = 0; j < s; ++j) {
      auto t = pq.top(); pq.pop();
      cout << t[1] + 1 << ' ';
      temp.push_back(t);
    }
    cout << '\n';
    for (auto t : temp) {
      t[0] -= 1;
      if (t[0] > 0) pq.push(t);
    }
  }
}

• Subtask 1: 6 / 6
• Subtask 2: 7 / 7
• Subtask 3: 12 / 12
• Subtask 4: 45 / 45
• Subtask 5: 15 / 15
• Subtask 6: 15 / 15