답안 #807253

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
807253	2023-08-04T15:16:30 Z	oscar1f	Cookies (JOI23_cookies)	C++17	12 / 100	1 ms	340 KB

cookies

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

const int MAX_SOM=20;//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;j++) { ///=MAX_SOM/possi[i]
            estPossi[i].push_back(toutZer);
        }
    }
    estPossi[0][0][0]=true;
    for (int i=0;i<nbPossi;i++) {
        for (int j=0;j<MAX_SOM;j++) { // A MODIFIER ENSUITE
            if (i!=0) {
                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 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

0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Incorrect	0 ms	340 KB	Output isn't correct
9	Halted	0 ms	0 KB	-

Subtask #2

0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Incorrect	0 ms	340 KB	Output isn't correct
6	Halted	0 ms	0 KB	-

Subtask #3

12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	1 ms	212 KB	Output is correct
17	Correct	1 ms	212 KB	Output is correct
18	Correct	0 ms	212 KB	Output is correct
19	Correct	1 ms	212 KB	Output is correct
20	Correct	0 ms	316 KB	Output is correct
21	Correct	0 ms	316 KB	Output is correct
22	Correct	1 ms	212 KB	Output is correct
23	Correct	0 ms	320 KB	Output is correct
24	Correct	1 ms	212 KB	Output is correct
25	Correct	0 ms	212 KB	Output is correct
26	Correct	0 ms	212 KB	Output is correct
27	Correct	1 ms	212 KB	Output is correct
28	Correct	0 ms	212 KB	Output is correct
29	Correct	1 ms	212 KB	Output is correct
30	Correct	1 ms	212 KB	Output is correct
31	Correct	1 ms	212 KB	Output is correct
32	Correct	0 ms	320 KB	Output is correct
33	Correct	0 ms	320 KB	Output is correct
34	Correct	1 ms	320 KB	Output is correct
35	Correct	1 ms	320 KB	Output is correct
36	Correct	1 ms	320 KB	Output is correct
37	Correct	1 ms	316 KB	Output is correct

Subtask #4

0 / 45.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Incorrect	0 ms	340 KB	Output isn't correct
9	Halted	0 ms	0 KB	-

Subtask #5

0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Incorrect	0 ms	340 KB	Output isn't correct
9	Halted	0 ms	0 KB	-

Subtask #6

0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Incorrect	0 ms	340 KB	Output isn't correct
9	Halted	0 ms	0 KB	-