Submission #807188

#	Time	Username	Problem	Language	Result	Execution time	Memory
807188		Arturgo	Cookies (JOI23_cookies)	C++14	100 / 100	177 ms	260032 KiB

cookies

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

const int MAX_COOKIES = 15000 + 1;
using bits = bitset<MAX_COOKIES>;

int nbTypes, nbBoites, nbCookies;
vector<int> tailles;

int profil[MAX_COOKIES], cumul[MAX_COOKIES];

priority_queue<pair<int, int>> nbs;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> nbTypes;
    
    for(int iType = 0;iType < nbTypes;iType++) {
        int nb;
        cin >> nb;
        nbs.push({nb, iType + 1});
        
        nbCookies += nb;
        for(int iDiff = 0;iDiff < nb;iDiff++) {
            profil[iDiff]++;
        }
    }
    
    for(int iCookie = 0;iCookie < nbCookies;iCookie++) {
        cumul[iCookie + 1] = cumul[iCookie] + profil[iCookie];
    }
    
    cin >> nbBoites;
    for(int iBoite = 0;iBoite < nbBoites;iBoite++) {
        int taille;
        cin >> taille;
        tailles.push_back(taille);
    }
    
    reverse(tailles.begin(), tailles.end());
    
    // iBoite, k, somme
    vector<vector<bits>> dyn;
    
    int minBoites = nbCookies + 1;
    int boiteOpt = 0;
    
    for(int iBoite = 0;iBoite < nbBoites;iBoite++) {
        vector<bits> curCouche;
        
        bits premLigne;
        premLigne[0] = 1;
        curCouche.push_back(premLigne);
        
        for(int k = 1;k * tailles[iBoite] <= nbCookies;k++) {
            bits curLigne = curCouche.back() << tailles[iBoite];
            
            if(!dyn.empty() && k < (int)dyn.back().size())
                curLigne |= dyn.back()[k];
            
            curLigne <<= (MAX_COOKIES - cumul[k] - 1);
            curLigne >>= (MAX_COOKIES - cumul[k] - 1);

            if(curLigne[nbCookies] && k < minBoites) {
                minBoites = k;
                boiteOpt = iBoite;
            }
            
            curCouche.push_back(curLigne);
        }
        
        dyn.push_back(curCouche);
    }
    
    if(minBoites > nbCookies) {
        cout << -1 << "\n";
        return 0;
    }
    
    cout << minBoites << "\n";
    
    // reconstruct the sizes
    
    int curBoite = boiteOpt;
    int curK = minBoites;
    int curSomme = nbCookies;
    
    vector<int> optTailles;
    
    while(curK != 0) {
        while(tailles[curBoite] <= curSomme && dyn[curBoite][curK - 1][curSomme - tailles[curBoite]]) {
            optTailles.push_back(tailles[curBoite]);
            curSomme -= tailles[curBoite];
            curK--;
        }
        curBoite--;
    }
    
    for(int taille : optTailles) {
        cout << taille << " ";
        
        vector<pair<int, int>> to_insert;
        for(int iElem = 0;iElem < taille;iElem++) {
            pair<int, int> p = nbs.top();
            nbs.pop();
            cout << p.second << " ";
            
            p.first--;
            if(p.first) {
                to_insert.push_back(p);
            }
        }
        
        for(pair<int, int> p : to_insert) {
            nbs.push(p);
        }
        
        cout << "\n";
    }
    
    return 0;
}

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