#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-j >= k)
curr += pra[n-k+1] - pra[j];
int l = 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 time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
184 ms |
262148 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
