#include <bits/stdc++.h>
#include "homecoming.h"
#define all(x) (x).begin(), (x).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<int, int> pii;
typedef pair<ld, ld> pld;
long long solve(int N, int K, int *A, int *B){
vector<ll> pre(2*N);
for(ll i = 0; i < 2*N; ++i){
pre[i] = B[i%N];
if(i)
pre[i] += pre[i-1];
}
vector<vector<ll>> dp(N, vector<ll>(2, -1e18));
ll ans = 0;
dp[0][1] = A[0]-pre[K-1];
for(int i = 1; i < N; ++i){
dp[i][0] = max(dp[i-1][0], dp[i-1][1]);
dp[i][1] = dp[i-1][0]+A[i]-pre[min(i+K-1, N-1)]+pre[i-1];
if(i+K-1 < N)
dp[i][1] = max(dp[i][1], dp[i-1][1]+A[i]-B[i+K-1]);
else
dp[i][1] = max(dp[i][1], dp[i-1][1]+A[i]);
dp[i][1] = max((ll)-1e18, dp[i][1]);
}
ans = max({ans, dp[N-1][0], dp[N-1][1]});
dp = vector<vector<ll>>(N, vector<ll>(2, -1e18));
dp[0][0] = 0;
for(int i = 1; i < N; ++i){
dp[i][0] = max(dp[i-1][0], dp[i-1][1]);
dp[i][1] = dp[i-1][0]+A[i]-pre[i+K-1]+pre[i-1];
dp[i][1] = max(dp[i][1], dp[i-1][1]+A[i]-B[(i+K-1)%N]);
dp[i][1] = max((ll)-1e18, dp[i][1]);
}
ans = max({ans, dp[N-1][0], dp[N-1][1]});
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
324 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
324 KB |
Output is correct |
6 |
Correct |
2 ms |
972 KB |
Output is correct |
7 |
Correct |
2 ms |
972 KB |
Output is correct |
8 |
Correct |
2 ms |
588 KB |
Output is correct |
9 |
Correct |
2 ms |
972 KB |
Output is correct |
10 |
Correct |
2 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
115 ms |
76288 KB |
Output is correct |
2 |
Correct |
6 ms |
844 KB |
Output is correct |
3 |
Runtime error |
383 ms |
262148 KB |
Execution killed with signal 9 |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
324 KB |
Output is correct |
6 |
Correct |
2 ms |
972 KB |
Output is correct |
7 |
Correct |
2 ms |
972 KB |
Output is correct |
8 |
Correct |
2 ms |
588 KB |
Output is correct |
9 |
Correct |
2 ms |
972 KB |
Output is correct |
10 |
Correct |
2 ms |
332 KB |
Output is correct |
11 |
Correct |
115 ms |
76288 KB |
Output is correct |
12 |
Correct |
6 ms |
844 KB |
Output is correct |
13 |
Runtime error |
383 ms |
262148 KB |
Execution killed with signal 9 |
14 |
Halted |
0 ms |
0 KB |
- |