Submission #836838

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
836838	2023-08-24T16:14:23 Z	alvingogo	Cookies (JOI23_cookies)	C++14	0 / 100	119 ms	169792 KB

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
#define int long long
using namespace std;

signed main(){
    AquA;
    int n;
    cin >> n;
    vector<int> a(n);
    int s=0;
    const int gd=15005;
    vector<int> c(gd);
    for(int i=0;i<n;i++){
        cin >> a[i];
        c[a[i]]++;
        s+=a[i];
    }
    for(int i=gd-2;i>=1;i--){
        c[i]+=c[i+1];
    }
    for(int i=2;i<gd;i++){
        c[i]+=c[i-1];
    }
    int m;
    cin >> m;
    vector<int> b(m+1);
    for(int i=1;i<=m;i++){
        cin >> b[i];
    }
    sort(b.begin()+1,b.end(),greater<int>());
    vector<vector<bitset<gd> > > bt(gd,vector<bitset<gd> >(m+1));
    vector<bitset<gd> > lp(gd);
    for(int i=1;i<gd;i++){
        lp[i]|=lp[i-1];
        for(int j=c[i-1]+1;j<=c[i];j++){
            lp[i][j]=1;
        }
    }
    bt[0][0][0]=1;
    for(int i=0;i<gd;i++){
        for(int j=0;j<m && i*(b[j+1])<gd;j++){
            bt[i][j+1]|=bt[i][j];
        }
        for(int j=1;j<=m && i*b[j]<gd;j++){
            bt[i+1][j]|=(bt[i][j]<<b[j])&lp[i+1];
        }
    }
    for(int i=0;i<gd;i++){
        for(int j=0;j<=m;j++){
            if(bt[i][j][s]){
                vector<int> k;
                while(i>0 && j>0){
                    if(i>0 && bt[i-1][j][s-b[j]]){
                        k.push_back(b[j]);
                        s-=b[j];
                        i--;
                    }
                    else{
                        j--;
                    }
                }
                p_q<pair<int,int> > pq;
                for(int f=0;f<n;f++){
                    pq.push({a[f],f});
                }
                cout << k.size() << "\n";
                for(auto h:k){
                    vector<pair<int,int> > d;
                    cout << h << ' ';
                    for(int p=0;p<h;p++){
                        d.push_back(pq.top());
                        pq.pop();
                    }
                    for(auto z:d){
                        pq.push({z.fs-1,z.sc});
                        cout << z.sc+1 << " ";
                    }
                    cout << "\n";
                }
                return 0;
            }
        }
    }
    cout << -1 << "\n";
    return 0;
}

Subtask #1
0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	70 ms	138944 KB	Output is correct
2	Runtime error	111 ms	169708 KB	Execution killed with signal 11
3	Halted	0 ms	0 KB	-

Subtask #2
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	35 ms	83812 KB	Output is correct
2	Runtime error	113 ms	169728 KB	Execution killed with signal 11
3	Halted	0 ms	0 KB	-

Subtask #3
0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	73 ms	138920 KB	Output is correct
2	Correct	37 ms	83836 KB	Output is correct
3	Runtime error	119 ms	169792 KB	Execution killed with signal 11
4	Halted	0 ms	0 KB	-