/**
Death gotta be easy cause life is hard
**/
#include <algorithm>
#include <iostream>
#include <assert.h>
#include <string.h>
#include <stdio.h>
#include <iomanip>
#include <utility>
#include <math.h>
#include <time.h>
#include <vector>
#include <set>
#include <map>
#include "homecoming.h"
#define fr first
#define sc second
#define mk make_pair
#define pb push_back
#define sz(s) (long long)s.size()
#define all(s) s.begin(), s.end()
using namespace std;
const long long N = 2e6 + 5;
long long n, k, a[N], b[N];
long long dp[N][2], pref[N], inf = 1e18, ans;
long long sum(long long i)
{
return pref[i + k - 1] - (i == 0 ? 0 : pref[i - 1]);
}
long long Main( bool fl )
{
for (long long i = 0; i < n + n; i++)
pref[i] = pref[i - 1] + b[i];
for (long long i = 0; i < n; i++)
dp[i][0] = dp[i][1] = -inf;
if (fl)
dp[0][1] = a[0] + sum(0);
else
dp[0][0] = 0;
ans = max(dp[0][1], dp[0][0]);
for (long long i = 1; i < n; i++)
{
dp[i][0] = dp[i - 1][0];
if (i >= k)
dp[i][0] = max(dp[i][0], dp[i - k][1]);
if (i + k - 1 < n)
dp[i][1] = max( dp[i - 1][1] + b[i + k - 1], dp[i - 1][0] + sum(i) ) + a[i];
else
{
if (fl)
dp[i][1] = max( dp[i - 1][1], dp[i - 1][0] + pref[n - 1] - pref[i - 1] ) + a[i];
else
dp[i][1] = max( dp[i - 1][1] + b[i + k - 1], dp[i - 1][0] + sum(i) ) + a[i];
}
ans = max(ans, dp[i][0]);
ans = max(ans, dp[i][1]);
}
return ans;
}
long long solve(long long N, long long K, long long A[], long long B[])
{
n = N, k = K;
for (long long i = 0; i < n; i++)
a[i] = A[i], b[i] = -B[i];
for (long long i = 0; i < n; i++)
b[i + n] = -B[i];
return max(Main(0), Main(1));
}
/**
1
3 2
40 80 100
140 0 20
**/
Compilation message
/tmp/ccdhD2BR.o: In function `main':
grader.cpp:(.text.startup+0xff): undefined reference to `solve(int, int, int*, int*)'
collect2: error: ld returned 1 exit status
