Submission #1086926

#TimeUsernameProblemLanguageResultExecution timeMemory
1086926vjudge1Uplifting Excursion (BOI22_vault)C++17
45 / 100
5041 ms4440 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long int const M = 350; int const MM = M*M; int const off = 340; int const off2 = off*off; ll A[2*M]; ll dp[2][2*MM]; int m; ll l; int main() { cin >> m >> l; for (int i = -m; i <= m; ++i) cin >> A[i+off]; ll zz = -l; for (int i = -m; i <= m; ++i) { zz += A[i+off] * i; } if (zz < 0) { l = -l; for (int i = -m; i < 0; ++i) { int j = -i; int idx = i+off, idx2 = j+off; swap(A[idx], A[idx2]); } } ll itm = 0; memset(dp, 0xc3, sizeof dp); dp[0][off2] = 0; int idp = 1; for (int i = -m; i <= m; ++i) { ll take = i <= 0 ? A[i+off] : min(A[i+off], max(0LL, l / i)); l -= take * i; A[i+off] -= take; itm += take; memcpy(dp[idp], dp[idp^1], sizeof dp[idp]); if (i != 0) { // try_add_to_dp A[i+off] for (int j = -m*m; j < -m*m+i; ++j) { deque<int> dq; dq.emplace_back(j); for (int k = j + i; k <= m*m; k += i) { while (dq.size() && (k-dq.front())/i > A[i+off]) dq.pop_front(); while (dq.size() && dp[idp^1][k+off2] >= dp[idp^1][dq.back()+off2]+(k-dq.back())/i) dq.pop_back(); dq.emplace_back(k); if (dq.size()) dp[idp][k+off2] = max(dp[idp][k+off2], dp[idp^1][dq.front()+off2] + (k-dq.front())/i); } //for (int k = 1; (k <= A[i+off]) && (j-k*i>=-m*m) && (j-k*i<=m*m); ++k) { // dp[idp][j+off2] = max(dp[idp][j+off2], dp[idp^1][j-k*i+off2] + k); //} } memcpy(dp[idp^1], dp[idp], sizeof dp[idp]); // try_delete_from_dp take if (i > 0) { for (int j = m*m; j >= -m*m; --j) { deque<int> dq; dq.emplace_back(j); for (int k = j-i; k >= -m*m; k -= i) { while (dq.size() && (dq.front()-k)/i > take) dq.pop_front(); while (dq.size() && dp[idp^1][k+off2] >= dp[idp^1][dq.back()+off2]-(dq.back()-k)/i) dq.pop_back(); dq.emplace_back(k); if (dq.size()) dp[idp][k+off2] = max(dp[idp][k+off2], dp[idp^1][dq.front()+off2] - (dq.front()-k)/i); } //for (int k = 1; (k <= take) && (j+k*i>=-m*m) && (j+k*i<=m*m); ++k) { // dp[idp][j+off2] = max(dp[idp][j+off2], dp[idp^1][j+k*i+off2] - k); //} } } else { for (int j = -m*m; j < -m*m+i; ++j) { deque<int> dq; dq.emplace_back(j); for (int k = j + i; k <= m*m; k += i) { while (dq.size() && (dq.front()-k)/i > take) dq.pop_front(); while (dq.size() && dp[idp^1][k+off2] >= dp[idp^1][dq.back()+off2]-(dq.back()-k)/i) dq.pop_back(); dq.emplace_back(k); if (dq.size()) dp[idp][k+off2] = max(dp[idp][k+off2], dp[idp^1][dq.front()+off2] - (dq.front()-k)/i); } } } } idp ^= 1; } idp ^= 1; if (l < -m*m || l > m*m || dp[idp][l+off2] < -1e9) { cout << "impossible\n"; } else { cout << (dp[idp][l+off2] + itm) << '\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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...