#include<bits/stdc++.h>
#include "homecoming.h"
using namespace std;
#define ll long long
#define fr first
#define sc second
#define pb push_back
#define ARRS ((ll)(2e6+100))
#define MAX ((ll)(1e12+100))
ll a[ARRS];
ll b[ARRS];
ll s[ARRS];
ll dp[ARRS][2];
ll sum(ll l,ll r){
return s[r]-s[l-1];
}
long long solve(int n, int K, int *B, int *A){
ll pas=0,p=0;
for(int i=1; i<=n; i++){
a[i]=A[i-1];
a[i+n]=A[i-1];
b[i]=B[i-1];
b[i+n]=B[i-1];
p-=a[i];
p+=b[i];
}
for(int i=1; i<=2*n; i++)s[i]=s[i-1]+a[i];
pas=max(pas,p);
// cout<<pas<<endl;
for(int s=0; s<n; s++){
dp[0][0]=0;
dp[0][1]=-MAX;
for(int i=1; i<=n; i++){
dp[i][0]=dp[i-1][0];
dp[i][1]=-MAX;
if(i>=K){
dp[i][1]=max(dp[i][1],dp[i-K][0]+b[i-K+1+s]-sum(i-K+1+s,i+s));
dp[i][1]=max(dp[i][1],dp[i-1][1]+b[i-K+1+s]-a[i+s]);
}
dp[i][0]=max(dp[i][0],dp[i][1]);
//cout<<dp[i][0]<<" "<<dp[i][1]<<endl;
}
pas=max(pas,dp[n][0]);
//cout<<endl;
}
return pas;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
376 KB |
Output is correct |
2 |
Correct |
4 ms |
488 KB |
Output is correct |
3 |
Correct |
2 ms |
488 KB |
Output is correct |
4 |
Correct |
3 ms |
564 KB |
Output is correct |
5 |
Correct |
3 ms |
640 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
376 KB |
Output is correct |
2 |
Correct |
4 ms |
488 KB |
Output is correct |
3 |
Correct |
2 ms |
488 KB |
Output is correct |
4 |
Correct |
3 ms |
564 KB |
Output is correct |
5 |
Correct |
3 ms |
640 KB |
Output is correct |
6 |
Correct |
81 ms |
920 KB |
Output is correct |
7 |
Correct |
102 ms |
1052 KB |
Output is correct |
8 |
Correct |
32 ms |
1052 KB |
Output is correct |
9 |
Correct |
150 ms |
1052 KB |
Output is correct |
10 |
Correct |
4 ms |
1052 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1071 ms |
35916 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
376 KB |
Output is correct |
2 |
Correct |
4 ms |
488 KB |
Output is correct |
3 |
Correct |
2 ms |
488 KB |
Output is correct |
4 |
Correct |
3 ms |
564 KB |
Output is correct |
5 |
Correct |
3 ms |
640 KB |
Output is correct |
6 |
Correct |
81 ms |
920 KB |
Output is correct |
7 |
Correct |
102 ms |
1052 KB |
Output is correct |
8 |
Correct |
32 ms |
1052 KB |
Output is correct |
9 |
Correct |
150 ms |
1052 KB |
Output is correct |
10 |
Correct |
4 ms |
1052 KB |
Output is correct |
11 |
Execution timed out |
1071 ms |
35916 KB |
Time limit exceeded |
12 |
Halted |
0 ms |
0 KB |
- |