Submission #895364

#	Time	Username	Problem	Language	Result	Execution time	Memory
895364		ksujay2	Cookies (JOI23_cookies)	C++17	85 / 100	1057 ms	882212 KiB

cookies

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int N; cin >> N;
    vector<int> A(N);
    int sm = 0;
    for(int i = 0; i < N; i++) {
        cin >> A[i]; 
        sm += A[i];
    }
    vector<int> cnt(sm + 1);
    for(int ai : A) cnt[ai]++;
    vector<int> lim(sm + 1);
    int left = N;
    for(int i = 1; i <= sm; i++) {
        lim[i] = lim[i - 1] + left;
        left -= cnt[i];
    }
    int M; cin >> M;
    vector<int> B(M);
    for(int i = 0; i < M; i++) cin >> B[i];

    
    vector<vector<int>> dp(sm + 1);
    for(int i = 0; i <= sm; i++) dp[i].resize(lim[i] + 1, -1);
    dp[0][0] = 0;
    for(int i = M - 1; i >= 0; i--) {
        for(int j = 0; j < sm; j++) {
            for(int k = j * B[i]; k < dp[j].size() && k + B[i] < dp[j + 1].size(); k++) {
                if(dp[j][k] != -1 && dp[j + 1][k + B[i]] == -1) {
                    dp[j + 1][k + B[i]] = B[i];
                }
            }
        }
    }
    int best = -1;
    for(int i = 0; i <= sm; i++) {
        if(sm < dp[i].size() && dp[i][sm] != -1) {
            best = i;
            break;
        }
    }
    cout << best << endl;
    if(best != -1) {
        vector<int> c;
        int curi = best, curj = sm;
        while(curi != 0) {
            c.push_back(dp[curi][curj]);
            curj -= dp[curi][curj];
            curi--;
        }
        set<pair<int, int>> s;
        for(int i = 0; i < N; i++) s.insert({A[i], i});
        for(int i = best - 1; i >= 0; i--) {
            auto p = s.rbegin();
            vector<int> changed;
            cout << c[i] << " ";
            for(int j = 0; j < c[i]; j++) {
                cout << (*p).second + 1 << " ";
                changed.push_back((*p).second);
                p++;
            }
            for(int j : changed) {
                s.erase({A[j], j});
                s.insert({--A[j], j});
            }
            cout << endl;
        }
        for(int i = 0; i < N; i++) assert(A[i] == 0);
    }
}

Compilation message (stderr)

cookies.cpp: In function 'int main()':
cookies.cpp:30:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |             for(int k = j * B[i]; k < dp[j].size() && k + B[i] < dp[j + 1].size(); k++) {
      |                                   ~~^~~~~~~~~~~~~~
cookies.cpp:30:64: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |             for(int k = j * B[i]; k < dp[j].size() && k + B[i] < dp[j + 1].size(); k++) {
      |                                                       ~~~~~~~~~^~~~~~~~~~~~~~~~~~
cookies.cpp:39:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |         if(sm < dp[i].size() && dp[i][sm] != -1) {
      |            ~~~^~~~~~~~~~~~~~

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