Submission #1021162

#	Time	Username	Problem	Language	Result	Execution time	Memory
1021162		erray	Cookies (JOI23_cookies)	C++17	13 / 100	85 ms	56488 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;
  }
  bs dec;
  for (auto x : B) {
    dec[SUM - x] = true;
  }
  vector<int> sizes;
  while (size > 0) {
    auto next = reach[size - 1] & (dec >> (SUM - sum));
    int next_sum = next._Find_first();
    assert(next_sum != SUM);
    sizes.push_back(sum - next_sum);
    sum = next_sum;
    --size;
  }
  sort(sizes.rbegin(), sizes.rend());  
  //reverse(sizes.begin(), sizes.end());
  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: 0 / 12
• Subtask 4: 0 / 45
• Subtask 5: 0 / 15
• Subtask 6: 0 / 15