#pragma GCC optimize("O3")
#include "homecoming.h"
#include<bits/stdc++.h>
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
typedef long long ll;
typedef long long ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<61);
const int inf=(1<<30);
const int nmax=1e5+50;
const int mod=1e9+7;
using namespace std;
int n,k,i,j,t1,i1,t;
ll f[505][505][2],a[505],b[505],p[505],cur,ans;
ll solve(int N,int K,int *A,int *B)
{
n=N,k=K,ans=0;
memset(f,0,sizeof(f));
for(i=1;i<=n;i++)a[i]=A[i-1];
for(i=1;i<=n;i++)
{
b[i]=B[i-1];
p[i]=p[i-1]+b[i];
}
for(i=1;i<=n;i++)
{
for(j=1;j<=i;j++)
{
f[i][j][0]=max(f[i-1][j][0],f[i-1][j][1]);
for(t=j-1;t<i;t++)
{
t1=(t+k-1)%n+1;
i1=(i+k-1)%n;
if(!t1)t1=n;
if(!i1)i1=n;
if(t+k-1<i)
{
if(i1>i)cur=p[i1]-p[i-1];
else cur=p[n]-p[i-1]+p[i1];
}
else if(t1>t && i1<i)cur=p[n]-p[t1-1]+p[i1];
else cur=p[i1]-p[t1-1];
f[i][j][1]=max(f[i][j][1],f[t][j-1][1]-cur+a[i]);
}
}
}
for(i=1;i<=n;i++)ans=max(ans,max(f[n][i][0],f[n][i][1]));
return ans;
}
/*int main()
{
//freopen("sol.in","r",stdin);
//freopen("sol.out","w",stdout);
ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
cin>>n>>k;
for(i=1;i<=n;i++)cin>>a[i];
for(i=1;i<=n;i++)
{
cin>>b[i];
p[i]=p[i-1]+b[i];
}
for(i=1;i<=n;i++)
{
for(j=1;j<=i;j++)
{
f[i][j][0]=max(f[i-1][j][0],f[i-1][j][1]);
for(t=j-1;t<i;t++)
{
t1=(t+k-1)%n+1;
i1=(i+k-1)%n;
if(!t1)t1=n;
if(!i1)i1=n;
if(t+k-1<i)
{
if(i1>i)cur=p[i1]-p[i-1];
else cur=p[n]-p[i-1]+p[i1];
}
else if(t1>t && i1<i)cur=p[n]-p[t1-1]+p[i1];
else cur=p[i1]-p[t1-1];
f[i][j][1]=max(f[i][j][1],f[t][j-1][1]-cur+a[i]);
}
}
}
for(i=1;i<=n;i++)ans=max(ans,(f[n][i][0],f[n][i][1]));
cout<<ans<<endl;
return 0;
}
/*
3 2
40 80 100
140 0 20
*/
Compilation message
homecoming.cpp:94:1: warning: "/*" within comment [-Wcomment]
/*
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
4352 KB |
Output is correct |
| 2 |
Incorrect |
201 ms |
4392 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
4352 KB |
Output is correct |
| 2 |
Incorrect |
201 ms |
4392 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
187 ms |
16384 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
4352 KB |
Output is correct |
| 2 |
Incorrect |
201 ms |
4392 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
