Submission #1036215

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036215		tvladm2009	Cookies (JOI23_cookies)	C++17	0 / 100	1 ms	464 KiB

cookies

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
const int N = 3000 + 7;
const int M = 15000 + 7;
 
int n, m, a[M], b[M];
int vertical[M];
 
struct MyBitset {
    vector<ll> b;
    int n;
 
    void resize(int nn) {
        n = nn;
        b.resize(n / 63 + 2, 0);
    }
 
    void set(int x) {
        b[x / 63] |= (1LL << (x % 63));
    }
 
    bool get(int x) {
        if (x > n) {
            return 0;
        }
        if (b[x / 63] & (1LL << (x % 63))) {
            return true;
        } else {
            return false;
        }
    }
};
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    cin >> m;
    for (int i = 1; i <= m; ++i) cin >> b[i];
    
    int sumA = 0;
    for (int i = 1; i <= n; ++i) {
        sumA += a[i];
    }
    reverse(b + 1, b + m + 1);
    for (int i = 1; i <= sumA; ++i) {
        for (int j = 1; j <= n; ++j) {
            vertical[i] += min(i, a[j]);
        }
    }
    vector<bitset<M>> dp(sumA);
    bitset<M> full;
    for (int i = 0; i < M; ++i) full[i] = 1;

    dp[0][0] = 1;
    for (int i = 1; i <= m; ++i) {
        for (int c = 1; c <= (sumA - 1) / b[i]; ++c) {
            dp[c] |= (dp[c - 1] << b[i]);
            dp[c] &= full >> max(0, sumA - 1 - vertical[c]);
        }
    }
    for (int x = 1; x <= sumA; ++x) {
        if (dp[x][sumA] == 1) {
            cout << x << "\n";
            vector<pair<int, int>> boxes;
            int cnt = x;
            int sum = sumA;
            int pos = m;
            while (pos > 0) {
                while (cnt > 0 && dp[cnt - 1][sumA - b[pos]]) {
                    sumA -= b[pos];
                    cnt--;
                    boxes.push_back({b[pos], boxes.size()});
                }
                pos--;
            }
            vector<vector<int>> sol(boxes.size());
            for (int i = 1; i <= n; ++i) {
                sort(boxes.rbegin(), boxes.rend());
                int j = 0;
                while (a[i] > 0) {
                    if (j == boxes.size()) {
                        cout << i << "\n";
                        return 0;
                    }
                    if (boxes[j].first > 0) {
                        sol[boxes[j].second].push_back(i);
                        boxes[j].first--;
                        a[i]--;
                    }
                    j++;
                }
            }
            for (int i = 0; i < boxes.size(); ++i) {
                cout << sol[i].size() << " ";
                for (auto j : sol[i]) {
                    cout << j << " ";
                }
                cout << "\n";
            }
            return 0;
        }
    }
    cout << -1 << "\n";
    return 0;
}

Compilation message (stderr)

cookies.cpp: In function 'int main()':
cookies.cpp:87:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |                     if (j == boxes.size()) {
      |                         ~~^~~~~~~~~~~~~~~
cookies.cpp:99:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |             for (int i = 0; i < boxes.size(); ++i) {
      |                             ~~^~~~~~~~~~~~~~
cookies.cpp:72:17: warning: unused variable 'sum' [-Wunused-variable]
   72 |             int sum = sumA;
      |                 ^~~

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