Submission #381186

#TimeUsernameProblemLanguageResultExecution timeMemory
381186VodkaInTheJarHomecoming (BOI18_homecoming)C++14
13 / 100
1098 ms262148 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]; for (int p = j + 1; p <= n; p++) { curr -= b[p-1]; int nxt = p + k - 1; if (nxt > n) nxt -= n; if (nxt >= p || nxt < i) curr += a[p-1]; } for (int p = 1; p < i; p++) { curr -= b[p-1]; if (p + k - 1 < i) curr += a[p-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...