oj.uz

답안 #836848

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
836848 2023-08-24T16:16:26 Z alvingogo Cookies (JOI23_cookies) C++14
19 / 100
 430 ms 1048576 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
using namespace std;

int 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+1)*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

# 결과 실행 시간 메모리 Grader output
1 Correct 70 ms 138956 KB Output is correct
2 Correct 53 ms 83660 KB Output is correct
3 Correct 50 ms 83660 KB Output is correct
4 Correct 54 ms 83660 KB Output is correct
5 Correct 54 ms 111188 KB Output is correct
6 Correct 58 ms 111264 KB Output is correct
7 Correct 59 ms 138964 KB Output is correct
8 Correct 49 ms 83660 KB Output is correct
9 Correct 31 ms 83660 KB Output is correct
10 Runtime error 430 ms 1048576 KB Execution killed with signal 9
11 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 83668 KB Output is correct
2 Correct 51 ms 83772 KB Output is correct
3 Correct 48 ms 83668 KB Output is correct
4 Correct 47 ms 83676 KB Output is correct
5 Correct 46 ms 83796 KB Output is correct
6 Correct 36 ms 83660 KB Output is correct
7 Correct 46 ms 83660 KB Output is correct
8 Correct 47 ms 83668 KB Output is correct
9 Correct 48 ms 83796 KB Output is correct
10 Correct 56 ms 83920 KB Output is correct
11 Correct 52 ms 83776 KB Output is correct
12 Correct 47 ms 83668 KB Output is correct
13 Correct 46 ms 83752 KB Output is correct
14 Correct 42 ms 83772 KB Output is correct
15 Correct 43 ms 83728 KB Output is correct
16 Correct 37 ms 83704 KB Output is correct
17 Correct 38 ms 83760 KB Output is correct
18 Correct 41 ms 83788 KB Output is correct
19 Correct 48 ms 83788 KB Output is correct
20 Correct 37 ms 83772 KB Output is correct
21 Correct 36 ms 83836 KB Output is correct
22 Correct 37 ms 83700 KB Output is correct
23 Correct 36 ms 83720 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 62 ms 138936 KB Output is correct
2 Correct 37 ms 83668 KB Output is correct
3 Correct 47 ms 83660 KB Output is correct
4 Correct 53 ms 83660 KB Output is correct
5 Correct 45 ms 83684 KB Output is correct
6 Correct 56 ms 111264 KB Output is correct
7 Correct 52 ms 111256 KB Output is correct
8 Correct 61 ms 138948 KB Output is correct
9 Correct 59 ms 83844 KB Output is correct
10 Correct 59 ms 83788 KB Output is correct
11 Correct 42 ms 83660 KB Output is correct
12 Correct 45 ms 83656 KB Output is correct
13 Correct 45 ms 83684 KB Output is correct
14 Correct 50 ms 83660 KB Output is correct
15 Correct 63 ms 111252 KB Output is correct
16 Correct 52 ms 111176 KB Output is correct
17 Correct 65 ms 138932 KB Output is correct
18 Correct 56 ms 111164 KB Output is correct
19 Correct 69 ms 138976 KB Output is correct
20 Correct 63 ms 138980 KB Output is correct
21 Correct 64 ms 138860 KB Output is correct
22 Correct 70 ms 138956 KB Output is correct
23 Correct 62 ms 138976 KB Output is correct
24 Correct 62 ms 138956 KB Output is correct
25 Correct 65 ms 138996 KB Output is correct
26 Correct 59 ms 138964 KB Output is correct
27 Correct 63 ms 138964 KB Output is correct
28 Correct 83 ms 194188 KB Output is correct
29 Correct 61 ms 139004 KB Output is correct
30 Correct 63 ms 138932 KB Output is correct
31 Correct 100 ms 221580 KB Output is correct
32 Correct 74 ms 166360 KB Output is correct
33 Correct 75 ms 166452 KB Output is correct
34 Correct 72 ms 166416 KB Output is correct
35 Correct 121 ms 304540 KB Output is correct
36 Correct 166 ms 442504 KB Output is correct
37 Correct 51 ms 111180 KB Output is correct

Subtask #4
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 70 ms 138956 KB Output is correct
2 Correct 53 ms 83660 KB Output is correct
3 Correct 50 ms 83660 KB Output is correct
4 Correct 54 ms 83660 KB Output is correct
5 Correct 54 ms 111188 KB Output is correct
6 Correct 58 ms 111264 KB Output is correct
7 Correct 59 ms 138964 KB Output is correct
8 Correct 49 ms 83660 KB Output is correct
9 Correct 31 ms 83660 KB Output is correct
10 Runtime error 430 ms 1048576 KB Execution killed with signal 9
11 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 70 ms 138956 KB Output is correct
2 Correct 53 ms 83660 KB Output is correct
3 Correct 50 ms 83660 KB Output is correct
4 Correct 54 ms 83660 KB Output is correct
5 Correct 54 ms 111188 KB Output is correct
6 Correct 58 ms 111264 KB Output is correct
7 Correct 59 ms 138964 KB Output is correct
8 Correct 49 ms 83660 KB Output is correct
9 Correct 31 ms 83660 KB Output is correct
10 Runtime error 430 ms 1048576 KB Execution killed with signal 9
11 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 70 ms 138956 KB Output is correct
2 Correct 53 ms 83660 KB Output is correct
3 Correct 50 ms 83660 KB Output is correct
4 Correct 54 ms 83660 KB Output is correct
5 Correct 54 ms 111188 KB Output is correct
6 Correct 58 ms 111264 KB Output is correct
7 Correct 59 ms 138964 KB Output is correct
8 Correct 49 ms 83660 KB Output is correct
9 Correct 31 ms 83660 KB Output is correct
10 Runtime error 430 ms 1048576 KB Execution killed with signal 9
11 Halted 0 ms 0 KB -