oj.uz

답안 #836872

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
836872 2023-08-24T16:32:48 Z alvingogo Cookies (JOI23_cookies) C++14
7 / 100
 142 ms 216232 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];
    }
    vector<vector<bitset<gd> > > bt(gd+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].resize(m+1);
    bt[0][0][0]=1;
    for(int i=0;i<gd;i++){
        for(int j=0;j+1<bt[i].size();j++){
            bt[i][j+1]|=bt[i][j];
        }
        int cnt=0;
        for(int j=1;j<=m && (i+1)*b[j]<gd;j++){
            cnt=j;
        }
        bt[i+1].resize(cnt+1);
        for(int j=1;j<bt[i+1].size();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<bt[i].size();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;
}

Compilation message

cookies.cpp: In function 'int main()':
cookies.cpp:45:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::bitset<15005> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         for(int j=0;j+1<bt[i].size();j++){
      |                     ~~~^~~~~~~~~~~~~
cookies.cpp:53:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::bitset<15005> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |         for(int j=1;j<bt[i+1].size();j++){
      |                     ~^~~~~~~~~~~~~~~
cookies.cpp:58:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::bitset<15005> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |         for(int j=0;j<bt[i].size();j++){
      |                     ~^~~~~~~~~~~~~

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 142 ms 216168 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 62848 KB Output is correct
2 Correct 41 ms 83760 KB Output is correct
3 Correct 41 ms 83656 KB Output is correct
4 Correct 32 ms 69844 KB Output is correct
5 Correct 41 ms 83692 KB Output is correct
6 Correct 24 ms 56056 KB Output is correct
7 Correct 49 ms 83688 KB Output is correct
8 Correct 48 ms 83740 KB Output is correct
9 Correct 42 ms 83788 KB Output is correct
10 Correct 44 ms 83856 KB Output is correct
11 Correct 40 ms 83756 KB Output is correct
12 Correct 32 ms 69860 KB Output is correct
13 Correct 33 ms 69780 KB Output is correct
14 Correct 29 ms 65204 KB Output is correct
15 Correct 32 ms 69836 KB Output is correct
16 Correct 26 ms 58836 KB Output is correct
17 Correct 26 ms 58816 KB Output is correct
18 Correct 32 ms 63052 KB Output is correct
19 Correct 34 ms 65468 KB Output is correct
20 Correct 27 ms 56492 KB Output is correct
21 Correct 26 ms 56148 KB Output is correct
22 Correct 26 ms 56248 KB Output is correct
23 Correct 24 ms 56148 KB Output is correct

Subtask #3
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 142 ms 216232 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 142 ms 216168 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 142 ms 216168 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 142 ms 216168 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -