#ifndef safar
#include "homecoming.h"
#endif
using namespace std;
typedef long long ll;
const int NN = 2e6 + 10;
const ll Inf = 1e16;
ll dp[2][NN];
ll solve(int n, int k, int *A, int *B){
ll ans = 0;
ll S2 = 0;
for(int i = 0; i < n; i++) S2 += A[i];
for(int i = 0; i < n; i++) S2 -= B[i];
ans = max(ans, S2);
if(n == k){
return ans;
}
for(int it = 0; it <= n; it ++){
for(int j = 0; j + 1 < n; j ++) swap(A[j], A[j + 1]);
for(int j = 0; j + 1 < n; j ++) swap(B[j], B[j + 1]);
fill(dp[0], dp[0] + n + 1, -Inf);
fill(dp[1], dp[1] + n + 1, -Inf);
dp[0][0] = 0;
ll Sm = B[0];
for(int i = 1; i < n; i++){
Sm += B[i];
dp[0][i] = max(dp[0][i - 1], dp[1][i - 1]);
if(i >= k){
Sm -= B[i - k];
dp[1][i] = max(dp[1][i - 1] - B[i] + A[i - k + 1], dp[0][i-k] + A[i - k + 1] - Sm);
}
}
ans = max(ans, dp[0][n - 1] + dp[1][n - 1]);
}
return ans;
/*
fill(dp[0], dp[0] + n + 1, -Inf);
fill(dp[1], dp[1] + n + 1, -Inf);
dp[1][0] = 0;
Sm = 0;
for(int i = 0; i < k; i++) Sm += A[(n - i) % n];
for(int i = 1; i < n; i++){
Sm += A[i];
Sm -= A[(i - k + n) % n];
dp[1][i] = max(dp[0][i - 1], dp[1][i - 1]);
dp[0][i] = max(dp[0][i - 1] + B[i] - A[i], dp[1][i - 1] + B[i] - Sm);
}
S2 = 0;
for(int i = 0; i < n; i++) S2 += ((ll)A[i]) - B[i];
ans = max(ans, S2 + max(dp[0][n - 1], dp[1][n - 1]));
ans = max(ans, S2);
return ans;
*/
}
#ifdef safar
int Ai[3] = {0, 0, 1}, Bi[3] = {0, 2, 0};
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cout << solve(3, 2, Ai, Bi) << '\n';
return 0;
}
#endif
Compilation message
homecoming.cpp: In function 'll solve(int, int, int*, int*)':
homecoming.cpp:22:8: error: 'max' was not declared in this scope
ans = max(ans, S2);
^~~
homecoming.cpp:27:34: error: 'swap' was not declared in this scope
for(int j = 0; j + 1 < n; j ++) swap(A[j], A[j + 1]);
^~~~
homecoming.cpp:28:34: error: 'swap' was not declared in this scope
for(int j = 0; j + 1 < n; j ++) swap(B[j], B[j + 1]);
^~~~
homecoming.cpp:30:2: error: 'fill' was not declared in this scope
fill(dp[0], dp[0] + n + 1, -Inf);
^~~~
homecoming.cpp:30:2: note: suggested alternative: 'll'
fill(dp[0], dp[0] + n + 1, -Inf);
^~~~
ll
