Submission #1169324

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169324		mannshah1211	Cookies (JOI23_cookies)	C++20	100 / 100	279 ms	326080 KiB

cookies

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "deb.h"
#else
#define debug(...) 
#endif

void solve() {
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  vector<int> sorted_a(n);
  for (int i = 0; i < n; i++) {
    sorted_a[i] = a[i];
  }
  sort(sorted_a.rbegin(), sorted_a.rend());
  vector<int> pa(n + 1);
  for (int i = 1; i <= n; i++) {
    pa[i] = pa[i - 1] + sorted_a[i - 1];
  }
  int sum = pa[n];
  vector<bool> is(n + 1);
  int m;
  cin >> m;
  vector<int> b(m);
  for (int i = 0; i < m; i++) {
    cin >> b[i];
    is[b[i]] = true;
  }
  bitset<15001> ones;
  for (int i = 0; i <= 15000; i++) {
    ones.set(i, true);
  }
  vector<vector<bitset<15001>>> dp(n + 1);
  for (int i = 0; i <= n; i++) {
    dp[i] = vector<bitset<15001>>((i != 0) ? sum / i + 1 : sum + 1);
  }
  dp[n][0][sum] = true;
  for (int i = n; i >= 0; i--) {
    for (int j = 0; j <= ((i != 0) ? sum / i : sum); j++) {
      if (i != n && j <= sum / (i + 1)) {
        dp[i][j] |= dp[i + 1][j] >> j;
      }
      if (is[i] && j != 0) {
        dp[i][j] |= dp[i][j - 1];
      }
      dp[i][j] &= ones << pa[i];
    }
  }
  int mn = -1;
  for (int i = 0; i <= sum; i++) {
    if (dp[0][i][0]) {
      mn = i;
      break;
    }
  }
  if (mn == -1) {
    cout << -1 << '\n';
  } else {
    vector<int> sizes;
    int ptr_x = 0, ptr_y = mn, ptr_z = 0;
    while (ptr_x != n || ptr_y != 0) {
      if (ptr_x != n && ptr_y + ptr_z <= sum && dp[ptr_x + 1][ptr_y][ptr_z + ptr_y]) {
        ptr_x += 1;
        ptr_z += ptr_y;
      } else {
        ptr_y -= 1;
        sizes.push_back(ptr_x);
      }
    }
    vector<vector<int>> ans;
    priority_queue<pair<int, int>> pq;
    for (int i = 0; i < n; i++) {
      pq.emplace(a[i], i);
    }
    vector<int> rem = a;
    for (int sz : sizes) {
      vector<int> pack(sz, -1);
      for (int j = 0; j < sz; j++) {
        auto [item, idx] = pq.top();
        pq.pop();
        pack[j] = idx;
      }
      for (int j = 0; j < sz; j++) {
        rem[pack[j]] -= 1;
        if (rem[pack[j]] != 0) {
          pq.emplace(rem[pack[j]], pack[j]);
        } 
      }
      ans.push_back(pack);
    }
    cout << ans.size() << '\n';
    for (int i = 0; i < ans.size(); i++) {
      cout << ans[i].size() << " ";
      for (int item : ans[i]) {
        cout << item + 1 << " ";
      }
      cout << '\n';
    }
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int t = 1;
  // cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}

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