제출 #1348427

#제출 시각아이디문제언어결과실행 시간메모리
1348427MisterReaperCookies (JOI23_cookies)C++20
100 / 100
266 ms327156 KiB
#pragma GCC optimize("unroll-loops,O3")
#include <bits/stdc++.h>

using i64 = long long;

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

template<typename T>
bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

constexpr int max_N = 15000 + 5;

int N;
int A[max_N];
int M;
int B[max_N];
int have[max_N];

std::vector<std::bitset<max_N>> dp[max_N];
int sums[max_N];

std::bitset<max_N> setted_bitsets[max_N + 1];

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    setted_bitsets[0] = 0;
    for (int i = 1; i <= max_N; ++i) {
        setted_bitsets[i] = setted_bitsets[i - 1];
        setted_bitsets[i].set(i - 1);
    }

    std::cin >> N;
    for (int i = 0; i < N; ++i) {
        std::cin >> A[i];
    }
    std::cin >> M;
    for (int i = 0; i < M; ++i) {
        std::cin >> B[i];
        have[B[i]] = true;
    }

    int all = std::accumulate(A, A + N, 0);

    for (int i = 0; i < max_N; ++i) {
        for (int j = 0; j < N; ++j) {
            sums[i] += std::min(A[j], i);
        }
    }

    for (int i = 1; i < max_N; ++i) {
        dp[i].resize(all / i + 1);
    }

    dp[B[M - 1]][0][0] = true;
    
    for (int i = B[M - 1]; i >= 1; --i) {
        for (int j = 0; j <= all / i; ++j) {
            if (i - 1) {
                dp[i - 1][j] |= dp[i][j];
            }
            if (have[i] && j + 1 <= all / i && i <= sums[j + 1]) {
                dp[i][j + 1] |= (dp[i][j] & setted_bitsets[sums[j + 1] - i + 1]) << i;
            }
            // for (int k = 0; k <= all; ++k) {
            //     if (!dp[i][j][k]) {
            //         continue;
            //     }
            //     if (i - 1) {
            //         dp[i - 1][j][k] = true;
            //     }
            //     if (have[i] && k + i <= sums[j + 1]) {
            //         dp[i][j + 1][k + i] = true;
            //     }
            // }
        }
    }

    int cnt = 0;
    while (cnt <= all && !dp[1][cnt][all]) {
        cnt += 1;
    }

    debug(cnt);

    if (cnt == all + 1) {
        std::cout << "-1\n";
        return 0;
    }

    std::vector<int> taken;
    int a = 1, c = all;
    for (int b = cnt; b >= 1; --b) {
        while (a + 1 <= B[M - 1] && b <= all / (a + 1) && dp[a + 1][b][c]) {
            a += 1;
        }
        debug(a, b, c);
        assert(dp[a][b - 1][c - a]);
        taken.emplace_back(a);
        c -= a;
    }

    std::vector<std::vector<int>> ans;

    for (auto i : taken) {
        std::vector<int> p(N);
        std::iota(p.begin(), p.end(), 0);
        std::sort(p.begin(), p.end(), [&](auto lhs, auto rhs) {
            return A[lhs] > A[rhs];
        });
        ans.emplace_back();
        for (int j = 0; j < i; ++j) {
            A[p[j]] -= 1;
            ans.back().emplace_back(p[j]);
        }
    }

    std::cout << ans.size() << '\n';
    for (auto v : ans) {
        std::cout << v.size();
        for (auto i : v) {
            std::cout << ' ' << i + 1;
        }
        std::cout << '\n';
    }

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...