Submission #1094718

#TimeUsernameProblemLanguageResultExecution timeMemory
1094718not_amirUplifting Excursion (BOI22_vault)C++14
0 / 100
1 ms348 KiB
#include <bits/stdc++.h> using namespace std; vector<int> convolute(vector<int> a, vector<int> b) { int n = a.size(), m = b.size(); vector<int> ans(n + m + 1); for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) ans[i + j] = max(ans[i + j], a[i] + b[j]); return ans; } vector<int> ans(vector<int> p, int L, int D) { if(L <= 2 * D) { vector<int> res(D + 1); for(int i = 0; i <= D; i++) res[i] = p[i + L - D]; return res; } vector<int> q = ans(p, L / 2, D); if(L % 2) { vector<int> res = convolute(q, p); vector<int> newq(D + 1); for (int i = 0; i <= D; i++) newq[i] = res[i + 1]; q = newq; } vector<int> res = convolute(q, q); res.resize(D + 1); return res; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int m, L, jnk; cin >> m >> L; for(int i = 0; i < m; i++) { int x; cin >> x; if(x != 0) return 0; } cin >> jnk; vector<int> v, w; for(int i = 1; i <= m; i++) { int l, tpow = 1; cin >> l; while(l) { if(l % 2) v.push_back(tpow), w.push_back(tpow * i); tpow *= 2; l /= 2; } } int n = v.size(); vector<vector<int>> dp(n + 1, vector<int>(2 * m + 1)); for(int i = 1; i <= n; i++) { for(int j = 1; j <= 2 * m; j++) { dp[i][j] = dp[i - 1][j]; if(j >= w[i - 1]) dp[i][j] = max(dp[i][j],dp[i][j - w[i - 1]] + v[i - 1]); } } vector<int> p(2 * m + 1); for(int i = 0; i <= 2 * m; i++) p[i] = dp[n][i]; cout << ans(p, L, m).back() + jnk + 1; }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...