| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 836900 | 2023-08-24T17:00:32 Z | alvingogo | Cookies (JOI23_cookies) | C++14 | 39 ms | 58352 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];
}
reverse(b.begin()+1,b.end());
vector<vector<bitset<gd> > > bt(m+1);
vector<bitset<gd> > lp(gd+1);
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(1);
bt[0][0][0]=1;
for(int i=0;i<m;i++){
bt[i+1].resize(s/(b[i+1])+1);
for(int j=0;j<bt[i].size();j++){
bt[i+1][j]|=bt[i][j];
}
for(int j=1;j<bt[i+1].size();j++){
bt[i+1][j]|=(bt[i+1][j-1]<<b[i+1])&lp[j];
}
}
for(int i=0;i<=m;i++){
for(int j=0;j<bt[i].size();j++){
if(bt[i][j][s]){
vector<int> k;
while(i>0 && j>0){
if(bt[i-1][j][s]){
i--;
}
else{
k.push_back(b[i]);
s-=b[i];
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 | 13 ms | 27996 KB | Output is correct |
| 2 | Correct | 15 ms | 27948 KB | Output is correct |
| 3 | Correct | 13 ms | 27964 KB | Output is correct |
| 4 | Correct | 14 ms | 27964 KB | Output is correct |
| 5 | Correct | 14 ms | 27908 KB | Output is correct |
| 6 | Correct | 14 ms | 27988 KB | Output is correct |
| 7 | Correct | 14 ms | 27988 KB | Output is correct |
| 8 | Runtime error | 39 ms | 58316 KB | Execution killed with signal 11 |
| 9 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 14 ms | 27988 KB | Output is correct |
| 2 | Correct | 14 ms | 27992 KB | Output is correct |
| 3 | Correct | 13 ms | 27988 KB | Output is correct |
| 4 | Correct | 13 ms | 27988 KB | Output is correct |
| 5 | Runtime error | 39 ms | 58352 KB | Execution killed with signal 11 |
| 6 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 14 ms | 27932 KB | Output is correct |
| 2 | Correct | 13 ms | 27988 KB | Output is correct |
| 3 | Correct | 13 ms | 27936 KB | Output is correct |
| 4 | Correct | 14 ms | 27988 KB | Output is correct |
| 5 | Correct | 14 ms | 27996 KB | Output is correct |
| 6 | Correct | 14 ms | 27948 KB | Output is correct |
| 7 | Correct | 14 ms | 27888 KB | Output is correct |
| 8 | Correct | 14 ms | 27992 KB | Output is correct |
| 9 | Correct | 14 ms | 27988 KB | Output is correct |
| 10 | Correct | 13 ms | 27876 KB | Output is correct |
| 11 | Correct | 14 ms | 27944 KB | Output is correct |
| 12 | Correct | 14 ms | 28008 KB | Output is correct |
| 13 | Correct | 15 ms | 27968 KB | Output is correct |
| 14 | Correct | 13 ms | 27920 KB | Output is correct |
| 15 | Correct | 13 ms | 28004 KB | Output is correct |
| 16 | Correct | 14 ms | 27988 KB | Output is correct |
| 17 | Correct | 14 ms | 28000 KB | Output is correct |
| 18 | Correct | 14 ms | 28000 KB | Output is correct |
| 19 | Correct | 14 ms | 27992 KB | Output is correct |
| 20 | Correct | 13 ms | 27988 KB | Output is correct |
| 21 | Incorrect | 13 ms | 27988 KB | Too many cookies.. |
| 22 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 13 ms | 27996 KB | Output is correct |
| 2 | Correct | 15 ms | 27948 KB | Output is correct |
| 3 | Correct | 13 ms | 27964 KB | Output is correct |
| 4 | Correct | 14 ms | 27964 KB | Output is correct |
| 5 | Correct | 14 ms | 27908 KB | Output is correct |
| 6 | Correct | 14 ms | 27988 KB | Output is correct |
| 7 | Correct | 14 ms | 27988 KB | Output is correct |
| 8 | Runtime error | 39 ms | 58316 KB | Execution killed with signal 11 |
| 9 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 13 ms | 27996 KB | Output is correct |
| 2 | Correct | 15 ms | 27948 KB | Output is correct |
| 3 | Correct | 13 ms | 27964 KB | Output is correct |
| 4 | Correct | 14 ms | 27964 KB | Output is correct |
| 5 | Correct | 14 ms | 27908 KB | Output is correct |
| 6 | Correct | 14 ms | 27988 KB | Output is correct |
| 7 | Correct | 14 ms | 27988 KB | Output is correct |
| 8 | Runtime error | 39 ms | 58316 KB | Execution killed with signal 11 |
| 9 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 13 ms | 27996 KB | Output is correct |
| 2 | Correct | 15 ms | 27948 KB | Output is correct |
| 3 | Correct | 13 ms | 27964 KB | Output is correct |
| 4 | Correct | 14 ms | 27964 KB | Output is correct |
| 5 | Correct | 14 ms | 27908 KB | Output is correct |
| 6 | Correct | 14 ms | 27988 KB | Output is correct |
| 7 | Correct | 14 ms | 27988 KB | Output is correct |
| 8 | Runtime error | 39 ms | 58316 KB | Execution killed with signal 11 |
| 9 | Halted | 0 ms | 0 KB | - |