Submission #788127

#TimeUsernameProblemLanguageResultExecution timeMemory
788127model_codeCookies (JOI23_cookies)C++17
100 / 100
268 ms325988 KiB
/* FULL-SCORE SOLUTION OF "COOKIES" - Dynamic programming & construction of answer using greedy algorithm - Speedup DP using "harmonic series" - Speedup DP using bitset - Time Complexity: O(sumA^2 log N) * 1/64 */ #include <queue> #include <bitset> #include <vector> #include <iostream> #include <algorithm> using namespace std; vector<vector<int> > solve(int N, int M, const vector<int>& A, const vector<int>& B) { // step #1. preparation vector<int> SA = A; sort(SA.begin(), SA.end(), greater<int>()); vector<int> LA(N + 1); for (int i = 0; i < N; i++) { LA[i + 1] = LA[i] + SA[i]; } int S = LA[N]; vector<bool> changer(N + 1, false); for (int i = 0; i < M; i++) { changer[B[i]] = true; } // step #2. dynamic programming bitset<15001> allone = ~bitset<15001>(); vector<vector<bitset<15001> > > dp(N + 1); // dp[pos][height][sum], height <= S / pos for (int i = 0; i <= N; i++) { dp[i] = vector<bitset<15001> >(i != 0 ? S / i + 1 : S + 1); } dp[N][0][S] = 1; for (int i = N; i >= 0; i--) { for (int j = 0; j <= (i != 0 ? S / i : S); j++) { if (i != N && j <= S / (i + 1)) { dp[i][j] |= dp[i + 1][j] >> j; } if (changer[i] && j != 0) { dp[i][j] |= dp[i][j - 1]; } dp[i][j] &= allone << LA[i]; } } int min_boxes = -1; for (int i = 0; i <= S; i++) { if (dp[0][i][0]) { min_boxes = i; break; } } if (min_boxes == -1) { return vector<vector<int> >(); } // step #3. restoration vector<int> boxsize; int px = 0, py = min_boxes, pz = 0; while (!(px == N && py == 0)) { if (px != N && pz + py <= S && dp[px + 1][py][pz + py]) { px += 1; pz += py; } else { py -= 1; boxsize.push_back(px); } } // step #4. greedy algorithm vector<vector<int> > answer; priority_queue<pair<int, int> > que; for (int i = 0; i < N; i++) { que.push(make_pair(A[i], i)); } vector<int> remA = A; for (int s : boxsize) { vector<int> pack(s, -1); for (int j = 0; j < s; j++) { pair<int, int> u = que.top(); que.pop(); pack[j] = u.second; } for (int j = 0; j < s; j++) { remA[pack[j]] -= 1; if (remA[pack[j]] != 0) { que.push(make_pair(remA[pack[j]], pack[j])); } } answer.push_back(pack); } return answer; } int main() { int N; cin >> N; vector<int> A(N); for (int i = 0; i < N; i++) { cin >> A[i]; } int M; cin >> M; vector<int> B(M); for (int i = 0; i < M; i++) { cin >> B[i]; } vector<vector<int> > answer = solve(N, M, A, B); if (answer.empty()) { cout << -1 << '\n'; } else { cout << answer.size() << endl; for (vector<int> v : answer) { cout << v.size(); for (int i : v) { cout << ' ' << i + 1; } 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...