Submission #1086923

#TimeUsernameProblemLanguageResultExecution timeMemory
1086923vjudge1Uplifting Excursion (BOI22_vault)C++17
30 / 100
513 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; if (m > 100) return 0; // no sub6 for (int i = -m; i <= m; ++i) cin >> A[i+off]; ll zz = 0; for (int i = -m; i <= m; ++i) { zz += A[i+off] * i; } int rev = zz < 0; ll itm = 0; memset(dp, 0xc3, sizeof dp); dp[0][off2] = 0; int idp = 1; for (int i = rev ? m : -m; rev ? i >= -m : i <= m; i += rev ? -1 : 1) { ll cut = i ? min(A[i+off], max(0ll, l/i)) : 0; ll take = rev ? (i>=0?A[i+off]:cut) : (i<=0?A[i+off]:cut); 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; ++j) { 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 for (int j = -m*m; j <= m*m; ++j) { 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); } } } 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...