Submission #1147457

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147457		ParsaGolestani	Cookies (JOI23_cookies)	C++20	13 / 100	150 ms	1348 KiB

cookies

#include <bits/stdc++.h>
using namespace std;

const int N = 500;
const int S = 15000;

int n, m, a[N + 10], b[N + 10];
int dp[N + 10], par[N + 10];
pair<int, int> cnt[S + 10];
vector<int> vec[S + 10];

void readInput() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    cin >> m;
    for (int i = 1; i <= m; i++)
        cin >> b[i];
}

void calcDP() {
    dp[0] = 1;
    for (int i = 1; i <= m; i++)
        for (int j = b[i]; j <= n; j++)
            if (dp[j - b[i]] && (!dp[j] || dp[j - b[i]] + 1 < dp[j])) {
                dp[j] = dp[j - b[i]] + 1;
                par[j] = b[i];
            }
}

void solveSub1() {
    if (dp[n] == 0) {
        cout << -1 << flush;
        return;
    }
    vector<int> vec;
    int pnt = n;
    while (pnt) {
        vec.push_back(par[pnt]);
        pnt -= par[pnt];
    }
    int tmp = 1;
    cout << vec.size() << '\n';
    for (auto x: vec) {
        cout << x << ' ';
        for (int i = 1; i <= x; i++) {
            cout << tmp << ' ';
            tmp++;
        }
        cout << '\n';
    }
}

void solveSub2() {
    int sum = 0;
    for (int i = 1; i <= n; i++)
        sum += a[i];
    if (sum % b[1]) {
        cout << -1 << flush;
        return;
    }
    int ans = sum / b[1];
    for (int i = 1; i <= ans; i++)
        cnt[i] = {b[1], i};
    for (int i = 1; i <= n; i++) {
        for (int j = ans; j >= 1; j--)
            if (a[i] && cnt[j].first) {
                a[i]--;
                cnt[j].first--;
                vec[cnt[j].second].push_back(i);
            }
        if (a[i]) {
            cout << -1 << flush;
            return;
        }
        sort(cnt + 1, cnt + ans + 1);
    }
    cout << ans << '\n';
    for (int i = 1; i <= ans; i++) {
        cout << b[1] << ' ';
        for (auto x: vec[i])
            cout << x << ' ';
        cout << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    readInput();
    if (*max_element(a + 1, a + n + 1) == 1) {
        calcDP();
        solveSub1();
    }
    else if (m == 1)
        solveSub2();
    return 0;
}

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