#include<bits/stdc++.h>
#include "homecoming.h"
using namespace std;
long long N1;
long long sa[2000009], sb[2000009];
long long Sb(long long l, long long r){
while(l >= N1) l -=N1;
while(r >= N1) r -=N1;
if(!l) return sb[r];
if(l <= r) return sb[r] - sb[l-1];
return sb[N1-1] - sb[l - 1] + sb[r];
}
long long Sa(long long l, long long r){
while(l >= N1) l -=N1;
while(r >= N1) r -=N1;
if(!l) return sa[r];
if(l <= r) return sa[r] - sa[l-1];
return sa[N1-1] - sa[l - 1] + sa[r];
}
long long su(long long l, long long r){
return Sa(l,r) - Sb(l,r);
}
long long M[2000009];
long long T[2000009];
long long dp[4000009][2];
long long A1[6000009];
long long B1[6000009];
long long long long solve(long long N, long long K, long long *A, long long *B){
N1 = N;
for(long long i = 0; i < N; i++)
A1[i] = A[i],
B1[i] = B[i];
for(long long i = 0; i < 2*N; i++)
A1[i+N] = A1[i],
B1[i+N] = B1[i];
sa[0] = A1[0];
sb[0] = B1[0];
for(long long i = 1; i < N; i++)
sa[i] = sa[i-1] + A1[i],
sb[i] = sb[i-1] + B1[i],
T[i] = A1[i] - B1[i];
if(N == K) return max((long long)0, sa[N-1] - sb[N-1]);
deque<pair<long long,long long> > q;
long long H = 0, D = 0;
for(long long i = N-K-1; i >= 0; i--){
H += T[i];
if(H > q.front().first) q.push_front({T[i],i});
}
for(long long i = N-K-1; i < N+N-K-1; i++){
M[i%N] = q.front().second ;
if(q.front().second == i-N+K+1) q.pop_front();
D += T[i%N];
long long p = T[i%N] - D;
while(q.size() && q.back().first <= p) q.pop_back();
q.push_back({p,i%N});
}
long long masof = 1e18, FI = -1;
for(long long i = 0; i < N; i++){
long long le = M[i];
long long si = i - le;
if(si < 0) si += N;
if(si < masof) masof = si, FI = i;
}
FI -= N;
dp[FI][0] = -1e18;
dp[FI][1] = A1[FI] - Sb(FI, FI+K-1);
for(long long i = FI + 1; i < FI + N - K; i++){
dp[i][0] = max(dp[i-1][0] , dp[i-1][1]);
dp[i][1] = dp[i-1][1] + A1[i] - B1[i + K - 1];
if(i - K >= FI) dp[i][1] =max(dp[i][1],
max(dp[i - K][0] , dp[i - K][1]) +
A1[i] - Sb(i, i+K-1));
}
long long ans = max(dp[FI + N - K - 1][0], dp[FI+ N - K - 1][1]);
long long s = 0;
for(long long i = FI - 1; i > FI - N + K; i --){
s += A1[i+N] - B1[i+N];
ans =max(ans, s + max(dp[i + N - K - 1][0], dp[i + N - K - 1][1]));
}
return max(max((long long)0,ans), sa[N-1]-sb[N-1]);
return 0;
}
Compilation message
homecoming.cpp:28:11: error: 'long long long' is too long for GCC
long long long long solve(long long N, long long K, long long *A, long long *B){
^~~~
homecoming.cpp:28:16: error: 'long long long' is too long for GCC
long long long long solve(long long N, long long K, long long *A, long long *B){
^~~~
