답안 #807263

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
807263	2023-08-04T15:20:52 Z	oscar1f	Cookies (JOI23_cookies)	C++17	19 / 100	198 ms	192688 KB

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 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	68 ms	53568 KB	Output is correct
2	Correct	31 ms	30596 KB	Output is correct
3	Correct	31 ms	30592 KB	Output is correct
4	Correct	15 ms	15516 KB	Output is correct
5	Correct	48 ms	44396 KB	Output is correct
6	Correct	28 ms	32132 KB	Output is correct
7	Correct	50 ms	43068 KB	Output is correct
8	Correct	31 ms	30724 KB	Output is correct
9	Correct	1 ms	468 KB	Output is correct
10	Correct	198 ms	192688 KB	Output is correct
11	Correct	17 ms	20692 KB	Output is correct
12	Correct	109 ms	103748 KB	Output is correct
13	Runtime error	58 ms	49616 KB	Execution killed with signal 11
14	Halted	0 ms	0 KB	-

Subtask #2

7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	7964 KB	Output is correct
2	Correct	31 ms	30584 KB	Output is correct
3	Correct	33 ms	30588 KB	Output is correct
4	Correct	15 ms	15592 KB	Output is correct
5	Correct	38 ms	30648 KB	Output is correct
6	Correct	1 ms	468 KB	Output is correct
7	Correct	36 ms	30612 KB	Output is correct
8	Correct	30 ms	30572 KB	Output is correct
9	Correct	34 ms	30592 KB	Output is correct
10	Correct	48 ms	30596 KB	Output is correct
11	Correct	30 ms	30680 KB	Output is correct
12	Correct	15 ms	15592 KB	Output is correct
13	Correct	14 ms	15536 KB	Output is correct
14	Correct	12 ms	15592 KB	Output is correct
15	Correct	14 ms	15592 KB	Output is correct
16	Correct	4 ms	4212 KB	Output is correct
17	Correct	3 ms	4212 KB	Output is correct
18	Correct	15 ms	7972 KB	Output is correct
19	Correct	22 ms	15556 KB	Output is correct
20	Correct	5 ms	1004 KB	Output is correct
21	Correct	4 ms	596 KB	Output is correct
22	Correct	5 ms	744 KB	Output is correct
23	Correct	1 ms	596 KB	Output is correct

Subtask #3

12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	76 ms	53696 KB	Output is correct
2	Correct	7 ms	7964 KB	Output is correct
3	Correct	29 ms	30576 KB	Output is correct
4	Correct	32 ms	30620 KB	Output is correct
5	Correct	14 ms	15544 KB	Output is correct
6	Correct	44 ms	44448 KB	Output is correct
7	Correct	28 ms	32192 KB	Output is correct
8	Correct	44 ms	43120 KB	Output is correct
9	Correct	35 ms	30596 KB	Output is correct
10	Correct	35 ms	30604 KB	Output is correct
11	Correct	18 ms	15608 KB	Output is correct
12	Correct	15 ms	15592 KB	Output is correct
13	Correct	13 ms	15536 KB	Output is correct
14	Correct	15 ms	15592 KB	Output is correct
15	Correct	51 ms	44508 KB	Output is correct
16	Correct	30 ms	32132 KB	Output is correct
17	Correct	60 ms	53584 KB	Output is correct
18	Correct	21 ms	22532 KB	Output is correct
19	Correct	52 ms	46784 KB	Output is correct
20	Correct	38 ms	39076 KB	Output is correct
21	Correct	31 ms	28072 KB	Output is correct
22	Correct	28 ms	28040 KB	Output is correct
23	Correct	32 ms	27980 KB	Output is correct
24	Correct	56 ms	51368 KB	Output is correct
25	Correct	30 ms	27032 KB	Output is correct
26	Correct	28 ms	25768 KB	Output is correct
27	Correct	50 ms	45296 KB	Output is correct
28	Correct	49 ms	49180 KB	Output is correct
29	Correct	46 ms	42140 KB	Output is correct
30	Correct	45 ms	42080 KB	Output is correct
31	Correct	79 ms	69108 KB	Output is correct
32	Correct	28 ms	23836 KB	Output is correct
33	Correct	46 ms	42676 KB	Output is correct
34	Correct	33 ms	31944 KB	Output is correct
35	Correct	84 ms	63464 KB	Output is correct
36	Correct	105 ms	92968 KB	Output is correct
37	Correct	38 ms	37552 KB	Output is correct

Subtask #4

0 / 45.0

#	결과	실행 시간	메모리	Grader output
1	Correct	68 ms	53568 KB	Output is correct
2	Correct	31 ms	30596 KB	Output is correct
3	Correct	31 ms	30592 KB	Output is correct
4	Correct	15 ms	15516 KB	Output is correct
5	Correct	48 ms	44396 KB	Output is correct
6	Correct	28 ms	32132 KB	Output is correct
7	Correct	50 ms	43068 KB	Output is correct
8	Correct	31 ms	30724 KB	Output is correct
9	Correct	1 ms	468 KB	Output is correct
10	Correct	198 ms	192688 KB	Output is correct
11	Correct	17 ms	20692 KB	Output is correct
12	Correct	109 ms	103748 KB	Output is correct
13	Runtime error	58 ms	49616 KB	Execution killed with signal 11
14	Halted	0 ms	0 KB	-

Subtask #5

0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	68 ms	53568 KB	Output is correct
2	Correct	31 ms	30596 KB	Output is correct
3	Correct	31 ms	30592 KB	Output is correct
4	Correct	15 ms	15516 KB	Output is correct
5	Correct	48 ms	44396 KB	Output is correct
6	Correct	28 ms	32132 KB	Output is correct
7	Correct	50 ms	43068 KB	Output is correct
8	Correct	31 ms	30724 KB	Output is correct
9	Correct	1 ms	468 KB	Output is correct
10	Correct	198 ms	192688 KB	Output is correct
11	Correct	17 ms	20692 KB	Output is correct
12	Correct	109 ms	103748 KB	Output is correct
13	Runtime error	58 ms	49616 KB	Execution killed with signal 11
14	Halted	0 ms	0 KB	-

Subtask #6

0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	68 ms	53568 KB	Output is correct
2	Correct	31 ms	30596 KB	Output is correct
3	Correct	31 ms	30592 KB	Output is correct
4	Correct	15 ms	15516 KB	Output is correct
5	Correct	48 ms	44396 KB	Output is correct
6	Correct	28 ms	32132 KB	Output is correct
7	Correct	50 ms	43068 KB	Output is correct
8	Correct	31 ms	30724 KB	Output is correct
9	Correct	1 ms	468 KB	Output is correct
10	Correct	198 ms	192688 KB	Output is correct
11	Correct	17 ms	20692 KB	Output is correct
12	Correct	109 ms	103748 KB	Output is correct
13	Runtime error	58 ms	49616 KB	Execution killed with signal 11
14	Halted	0 ms	0 KB	-