#include<bits/stdc++.h>
#include "homecoming.h"
using namespace std;
long long sa[60009], sb[60009];
long long su (long long l, long long r){
if(!l) return -sb[r]+sa[r];
return -sb[r] + sa[r] + sb[l-1] - sa[l-1];
}
long long Sb(long long l, long long r){
if(!l) return sb[r];
else return sb[r] - sb[l-1];
}
long long M[5009][22];
long long dp[40009][2];
int A1[2000009];
int B1[2000009];
long long int solve(int N, int K, int *A, int *B){
if(N > 1e5) return 1/0;
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 < 3*N; i++)
sa[i] = sa[i-1] + A1[i],
sb[i] = sb[i-1] + B1[i];
for(int i = 0 ;i < 2*N; i++)
M[i][0] = su(i,i);
for(long long i = 1; (1 << i) < 2*N; i++){
for(long long j = 0; j + (1<<i) - 1 < 2*N; j++){
long long m1 = M[j][i-1];
long long m2 = M[j+(1<<(i-1))][i-1];
M[j][i] = max(m2, m1 + su(j+(1<<i-1), j+(1<<i) - 1));
}
}
long long masof = 1e9, FI = -1;
for(long long i = N; i < 2*N; i++){
long long S = A1[i] - sb[i+K-1] + sb[i-1];
long long x = i, ss = 0;
for(long long L = 21; L >= 0; L--){
if(x - (1<<L) < 0) continue;
if(M[x - (1<<L)][L] + ss + S >= 0) continue;
ss += su(x - (1 << L), x -1);
x = x - (1 << L);
}
int l;
if(S >= 0) l = i;
else l = x - 1;
if(l <= i - N) l = -1;
if(l != -1 && masof > i - l) {
FI = i;
masof = i - l;
}
// cout << i <<" "<<l << " "<<S<<" "<<A1[i]<<" "<<sb[i+K-1]<<" "<<sb[i-1]<<endl;
}
// cout <<FI << endl;
if(FI == -1) return max((long long)0, sa[N-1] - sb[N-1]);
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)));
//cout << i <<" "<<dp[i][0] <<" "<<dp[i][1]<<endl;
}
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]));
}
//cout <<sa[N-1]<<" "<<sb[N-1]<<endl;
return max(max((long long)0,ans), sa[N-1]-sb[N-1]);
return 0;
}
Compilation message
homecoming.cpp: In function 'long long int solve(int, int, int*, int*)':
homecoming.cpp:18:25: warning: division by zero [-Wdiv-by-zero]
if(N > 1e5) return 1/0;
~^~
homecoming.cpp:37:46: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
M[j][i] = max(m2, m1 + su(j+(1<<i-1), j+(1<<i) - 1));
~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
616 KB |
Output is correct |
| 3 |
Correct |
3 ms |
616 KB |
Output is correct |
| 4 |
Correct |
2 ms |
760 KB |
Output is correct |
| 5 |
Incorrect |
3 ms |
760 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
616 KB |
Output is correct |
| 3 |
Correct |
3 ms |
616 KB |
Output is correct |
| 4 |
Correct |
2 ms |
760 KB |
Output is correct |
| 5 |
Incorrect |
3 ms |
760 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
40 ms |
8576 KB |
Execution killed with signal 4 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
616 KB |
Output is correct |
| 3 |
Correct |
3 ms |
616 KB |
Output is correct |
| 4 |
Correct |
2 ms |
760 KB |
Output is correct |
| 5 |
Incorrect |
3 ms |
760 KB |
Output isn't correct |
