Submission #829369

#TimeUsernameProblemLanguageResultExecution timeMemory
829369QwertyPiUplifting Excursion (BOI22_vault)C++14
80 / 100
5087 ms456076 KiB
#include <bits/stdc++.h> #pragma GCC optimize("unroll-loops") #pragma GCC optimize("Ofast") #define int long long using namespace std; const int M = 300 + 11; const int X = M * M * 2; const int INF = 1LL << 60; int a[M * 2]; int s[M * 2]; int norm(int x, int m){ if(x >= 0) return x; return (x % m + m) % m; } int dp_p[M][X], dp_n[M][X]; void solve(int m, int L, vector<int> a, int dp[M][X]){ for(int i = 0; i <= m; i++){ fill(dp[i], dp[i] + X, -INF); } for(int i = 1; i <= m; i++) s[i] = min(L, s[i - 1] + i * a[i]); dp[0][0] = 0; for(int i = 1; i <= m; i++){ for(int j = 0; j <= m * m + m * (i - 1); j++){ int left = norm(s[i] - s[i - 1] + j - a[i] * i, i); int right = min(s[i] + j - s[i - 1], m * m + m * i); int inc = i; int delta = ((s[i] - left) - (s[i - 1] - j)) / i; for(int k = left; k <= right; k += inc){ dp[i][k] = max(dp[i][k], dp[i - 1][j] + delta); delta--; } } } } int32_t main(){ int m, L; cin >> m >> L; for(int i = 0; i <= m * 2; i++) cin >> a[i]; if(L < 0){ reverse(a, a + m * 2 + 1); L = -L; } int sum_p = 0, sum_n = 0; for(int i = m + 1; i <= m * 2; i++) { sum_p += (i - m) * a[i]; } for(int i = m - 1; i >= 0; i--) { sum_n += (m - i) * a[i]; } if(sum_p < L){ cout << "impossible" << endl; return 0; } int lim = min(sum_n, sum_p - L); // positive vector<int> b_pos {0}, b_neg {0}; for(int i = 1; i <= m; i++){ b_pos.push_back(a[m + i]); b_neg.push_back(a[m - i]); } solve(m, lim + L, b_pos, dp_p); solve(m, lim, b_neg, dp_n); int ans = -INF; for(int i = 0; i <= m * m * 2; i++){ ans = max(ans, dp_p[m][i] + dp_n[m][i]); } if(L < 0){ cout << "impossible" << endl; return 0; } if(ans <= -INF / 2){ cout << "impossible" << endl; }else{ cout << a[m] + ans << endl; } }
#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...