Submission #807266

#	Time	Username	Problem	Language	Result	Execution time	Memory
807266		oscar1f	Cookies (JOI23_cookies)	C++17	100 / 100	238 ms	226012 KiB

cookies

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

const int MAX_SOM=15000+5;
using bits=bitset<MAX_SOM>;

int nbPiles,nbPossi,valNouv,somGlob,enCours,minPris,dernPris;
vector<int> possi,listePris;
vector<vector<bits>> estPossi;
bits toutZer;
int nbOccu[MAX_SOM],cumu[MAX_SOM];
set<pair<int,int>> etat,aRemettre;
set<pair<int,int>>::iterator it;

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>nbPiles;
    for (int i=0;i<nbPiles;i++) {
        cin>>valNouv;
        somGlob+=valNouv;
        nbOccu[valNouv]++;
        etat.insert({-valNouv,i+1});
    }
    enCours=nbPiles;
    for (int i=1;i<MAX_SOM;i++) {
        cumu[i]=cumu[i-1]+enCours;
        enCours-=nbOccu[i];
        //cout<<i<<" : "<<cumu[i]<<endl;
    }
    cin>>nbPossi;
    for (int i=0;i<nbPossi;i++) {
        cin>>valNouv;
        possi.push_back(valNouv);
    }
    reverse(possi.begin(),possi.end());
    for (int i=nbPossi-1;i>=0;i--) {
        estPossi.push_back({});
    }
    minPris=MAX_SOM;
    for (int i=0;i<nbPossi;i++) {
        for (int j=0;j<=MAX_SOM/possi[i];j++) {
            estPossi[i].push_back(toutZer);
        }
    }
    estPossi[0][0][0]=true;
    for (int i=0;i<nbPossi;i++) {
        for (int j=0;j<=MAX_SOM/possi[i];j++) { 
            if (i!=0 and possi[i-1]*j<=MAX_SOM) {
                estPossi[i][j]|=estPossi[i-1][j];
            }
            if (j!=0) {
                estPossi[i][j]|=(estPossi[i][j-1]<<possi[i]);
            }
            estPossi[i][j]<<=(MAX_SOM-1-cumu[j]);
            estPossi[i][j]>>=(MAX_SOM-1-cumu[j]);
            if (estPossi[i][j][somGlob] and j<minPris) {
                minPris=j;
                dernPris=i;
            }
            //cout<<i<<" "<<j<<" : "<<estPossi[i][j]<<endl;
        }
    }
    if (minPris==MAX_SOM) {
        cout<<-1<<endl;
        return 0;
    }
    cout<<minPris<<endl;
    while (minPris!=0) {
        if (dernPris!=0 and possi[dernPris-1]*minPris<=MAX_SOM and estPossi[dernPris-1][minPris][somGlob]) {
            dernPris--;
        }
        else {
            listePris.push_back(possi[dernPris]);
            somGlob-=possi[dernPris];
            minPris--;
        }
    }
    for (int i:listePris) {
        cout<<i<<" ";
        for (int j=0;j<i;j++) {
            it=etat.begin();
            cout<<(*it).second<<" ";
            aRemettre.insert({(*it).first+1,(*it).second});
            etat.erase(it);
        }
        for (auto k:aRemettre) {
            etat.insert(k);
        }
        aRemettre.clear();
        cout<<endl;
    }
}

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