Submission #807272

#TimeUsernameProblemLanguageResultExecution timeMemory
807272someoneCookies (JOI23_cookies)C++14
100 / 100
348 ms233656 KiB
#include <bits/stdc++.h> //#define int long long using namespace std; const int N = 1.5e4 + 42; vector<int> boite; vector<bitset<N>> dp[N]; int n, m, a[N], sz[N], prefix[N]; void remonter(int i, int j, int sum) { if(sum == 0) return; if(dp[i-1][j][sum - sz[j]]) { boite.push_back(-sz[j]); remonter(i-1, j, sum - sz[j]); } else { remonter(i, j+1, sum); } } void printSol() { priority_queue<pair<int, int>> pq; for(int i = 0; i < n; i++) pq.push({a[i], i}); cout << boite.size() << '\n'; for(int b : boite) { b = -b; cout << b << ' '; vector<int> ids; for(int j = 0; j < b; j++) { cout << pq.top().second+1 << ' '; ids.push_back(pq.top().second); pq.pop(); } for(int i : ids) pq.push({--a[i], i}); cout << '\n'; } } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n; for(int i = 0; i < n; i++) { cin >> a[i]; for(int j = 0; j < N; j++) prefix[j] += min(j, a[i]); } cin >> m; dp[0].resize(m); dp[0][m-1] = true; for(int i = 0; i < m; i++) cin >> sz[i]; int sum = prefix[N-1]; for(int i = 0; i <= sum; i++) { for(int j = m-1; j >= 0; j--) if(i * sz[j] <= sum) { dp[i+1].resize(j+1); j = 0; } for(int j = m-1; j >= 0; j--) if(i * sz[j] <= sum) { dp[i][j] <<= (N-prefix[i]-1); dp[i][j] >>= (N-prefix[i]-1); if(dp[i][j][sum]) { remonter(i, j, sum); printSol(); return 0; } if(j > 0) dp[i][j-1] |= dp[i][j]; if((i+1) * sz[j] <= sum) dp[i+1][j] |= (dp[i][j] << sz[j]); } } cout << -1 << '\n'; }
#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...