Submission #970688

#TimeUsernameProblemLanguageResultExecution timeMemory
970688huutuanCookies (JOI23_cookies)C++14
100 / 100
415 ms327080 KiB
#include<bits/stdc++.h> using namespace std; #ifdef sus const int N=100; #else const int N=15e3+10; #endif using bs=bitset<N>; vector<bs> f[N]; int n, m, a[N], b[N], pf[N], c[N], _a[N]; int32_t main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> n; for (int i=1; i<=n; ++i) cin >> _a[i]; cin >> m; for (int i=1; i<=m; ++i) cin >> b[i], c[b[i]]=1; for (int i=1; i<=n; ++i) a[i]=_a[i]; int sum=accumulate(a+1, a+n+1, 0); sort(a+1, a+n+1, greater<int>()); for (int i=1, j=n; i<=sum; ++i){ pf[i]=pf[i-1]+j; while (j && a[j]==i) --j; } f[0].resize(sum+1); for (int i=1; i<=sum; ++i){ f[i].resize(sum/i+1); } for (int i=0; i<=sum; ++i) f[0][i][0]=1; vector<int> sz; for (int i=1; i<=sum; ++i){ for (int j=sum/i; j>=0; --j){ if (i*(j+1)<=sum) f[i][j]|=f[i][j+1]; if (c[j]) f[i][j]|=f[i-1][j]<<j; for (int t=f[i][j]._Find_next(pf[i]); t<N; t=f[i][j]._Find_next(t)) f[i][j].set(t, 0); if (f[i][j].test(sum)){ int k=sum; while (i){ if (c[j] && k>=j && f[i-1][j].test(k-j)){ sz.push_back(j); --i; k-=j; }else ++j; } goto done; } } } cout << -1 << '\n'; return 0; done: reverse(sz.begin(), sz.end()); priority_queue<pair<int, int>> pq; vector<vector<int>> ans; for (int i=1; i<=n; ++i) a[i]=_a[i]; for (int i=1; i<=n; ++i) pq.emplace(a[i], i); for (int i:sz){ ans.emplace_back(); for (int j=0; j<i; ++j){ if (pq.empty()){ cout << -1 << '\n'; return 0; } ans.back().push_back(pq.top().second); pq.pop(); } for (int j:ans.back()){ --a[j]; if (a[j]) pq.emplace(a[j], j); } } cout << ans.size() << '\n'; for (auto &i:ans){ cout << i.size(); for (int j:i) cout << ' ' << j; cout << '\n'; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...