Submission #381183

#TimeUsernameProblemLanguageResultExecution timeMemory
381183VodkaInTheJarHomecoming (BOI18_homecoming)C++14
13 / 100
1108 ms262148 KiB
#include <bits/stdc++.h> #include "homecoming.h" using namespace std; 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); for (int i = 1; i <= n; i++) { dp[i][i-1] = 0; for (int j = i; j <= n; j++) { dp[i][j] = dp[i][j-1]; if (j - k + 1 < i) continue; long long sum = 0; for (int p = j - k + 2; p <= j; p++) sum -= b[p-1]; for (int p = j - k + 1; p >= i; p--) { sum -= b[p-1]; sum += a[p-1]; dp[i][j] = max(dp[i][j], sum + dp[i][p-1]); } } } 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...