| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 836863 | 2023-08-24T16:25:24 Z | alvingogo | Cookies (JOI23_cookies) | C++14 | 109 ms | 194336 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+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+5);
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
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 103 ms | 194092 KB | Output is correct |
| 2 | Correct | 98 ms | 194116 KB | Output is correct |
| 3 | Correct | 100 ms | 194124 KB | Output is correct |
| 4 | Correct | 93 ms | 180304 KB | Output is correct |
| 5 | Correct | 109 ms | 193948 KB | Output is correct |
| 6 | Incorrect | 97 ms | 184788 KB | Integer 0 violates the range [1, 4] |
| 7 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 88 ms | 173340 KB | Output is correct |
| 2 | Correct | 97 ms | 194124 KB | Output is correct |
| 3 | Correct | 100 ms | 194168 KB | Output is correct |
| 4 | Correct | 91 ms | 180272 KB | Output is correct |
| 5 | Correct | 100 ms | 194092 KB | Output is correct |
| 6 | Correct | 91 ms | 166484 KB | Output is correct |
| 7 | Correct | 102 ms | 194124 KB | Output is correct |
| 8 | Correct | 99 ms | 194184 KB | Output is correct |
| 9 | Correct | 106 ms | 194124 KB | Output is correct |
| 10 | Correct | 101 ms | 194336 KB | Output is correct |
| 11 | Correct | 107 ms | 194144 KB | Output is correct |
| 12 | Correct | 94 ms | 180292 KB | Output is correct |
| 13 | Correct | 93 ms | 180200 KB | Output is correct |
| 14 | Correct | 92 ms | 175692 KB | Output is correct |
| 15 | Correct | 95 ms | 180244 KB | Output is correct |
| 16 | Correct | 88 ms | 169192 KB | Output is correct |
| 17 | Correct | 90 ms | 169164 KB | Output is correct |
| 18 | Correct | 98 ms | 173384 KB | Output is correct |
| 19 | Correct | 94 ms | 175720 KB | Output is correct |
| 20 | Correct | 90 ms | 166884 KB | Output is correct |
| 21 | Correct | 89 ms | 166580 KB | Output is correct |
| 22 | Correct | 90 ms | 166676 KB | Output is correct |
| 23 | Correct | 103 ms | 166536 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 103 ms | 193996 KB | Output is correct |
| 2 | Correct | 91 ms | 173384 KB | Output is correct |
| 3 | Correct | 99 ms | 194156 KB | Output is correct |
| 4 | Correct | 99 ms | 194080 KB | Output is correct |
| 5 | Correct | 92 ms | 180244 KB | Output is correct |
| 6 | Correct | 107 ms | 194036 KB | Output is correct |
| 7 | Incorrect | 98 ms | 184800 KB | Integer 0 violates the range [1, 4] |
| 8 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 103 ms | 194092 KB | Output is correct |
| 2 | Correct | 98 ms | 194116 KB | Output is correct |
| 3 | Correct | 100 ms | 194124 KB | Output is correct |
| 4 | Correct | 93 ms | 180304 KB | Output is correct |
| 5 | Correct | 109 ms | 193948 KB | Output is correct |
| 6 | Incorrect | 97 ms | 184788 KB | Integer 0 violates the range [1, 4] |
| 7 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 103 ms | 194092 KB | Output is correct |
| 2 | Correct | 98 ms | 194116 KB | Output is correct |
| 3 | Correct | 100 ms | 194124 KB | Output is correct |
| 4 | Correct | 93 ms | 180304 KB | Output is correct |
| 5 | Correct | 109 ms | 193948 KB | Output is correct |
| 6 | Incorrect | 97 ms | 184788 KB | Integer 0 violates the range [1, 4] |
| 7 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 103 ms | 194092 KB | Output is correct |
| 2 | Correct | 98 ms | 194116 KB | Output is correct |
| 3 | Correct | 100 ms | 194124 KB | Output is correct |
| 4 | Correct | 93 ms | 180304 KB | Output is correct |
| 5 | Correct | 109 ms | 193948 KB | Output is correct |
| 6 | Incorrect | 97 ms | 184788 KB | Integer 0 violates the range [1, 4] |
| 7 | Halted | 0 ms | 0 KB | - |