Submission #381196

#TimeUsernameProblemLanguageResultExecution timeMemory
381196VodkaInTheJarHomecoming (BOI18_homecoming)C++14
31 / 100
203 ms262144 KiB
#include <bits/stdc++.h> #include "homecoming.h" using namespace std; const long long inf = 1e18; long long solve(int n, int k, int *a, int *b) { vector <vector <long long> > dp(n+1); for (int i = 1; i <= n; i++) dp[i].resize(n+1); vector <long long> pra(n+1, 0), prb(n+1, 0); for (int i = 1; i <= n; i++) { pra[i] = pra[i-1] + a[i-1]; prb[i] = prb[i-1] + b[i-1]; } for (int i = 1; i <= n; i++) { dp[i][i-1] = 0; long long curr_max = -inf; for (int j = i; j <= n; j++) { dp[i][j] = dp[i][j-1]; if (j - k + 1 < i) continue; int pos = j - k + 1; curr_max = max(curr_max, prb[pos-1] - pra[pos-1] + dp[i][pos-1]); dp[i][j] = max(dp[i][j], curr_max - prb[j] + pra[pos]); } } long long bb = 0; for (int i = 1; i <= n; i++) { bb -= b[i-1]; bb += a[i-1]; } long long ans = max(bb, dp[1][n]); for (int i = 1; i <= n; i++) { for (int j = i; j <= n; j++) { long long curr = dp[i][j]; curr -= prb[i-1]; curr -= prb[n] - prb[j]; if (i-1 >= k) curr += pra[i-k]; if (n-k+1 > j) curr += pra[n-k+1] - pra[j]; int l = max(j+1, n - k + 2), r = min(n, i+n-k); if (l <= r) curr += pra[r] - pra[l-1]; ans = max(ans, curr); } } return ans; } /* const int maxn = 1e3 + 3; int n, k; int a[maxn], b[maxn]; int main() { cin >> n >> k; for (int i = 0; i < n; i++) cin >> a[i] >> b[i]; cout << solve(n, k, a, b) << 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...