제출 #1348424

#제출 시각아이디문제언어결과실행 시간메모리
1348424MisterReaperCookies (JOI23_cookies)C++20
63 / 100
96 ms10804 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 = 500 + 5;

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

int dp[max_N][max_N][max_N];
int sums[max_N];

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

    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];
    }

    std::reverse(B, B + M);

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

    dp[0][0][0] = true;
    
    for (int i = 0; i < max_N; ++i) {
        for (int j = 0; j < M; ++j) {
            for (int k = 0; k < max_N; ++k) {
                if (!dp[i][j][k]) {
                    continue;
                }
                dp[i][j + 1][k] = true;
                if (k + B[j] <= sums[i]) {
                    dp[i + 1][j][k + B[j]] = true;
                }
            }
        }
    }

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

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

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

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

    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...