Submission #64142

#	Time	Username	Problem	Language	Result	Execution time	Memory
64142		Bodo171	Homecoming (BOI18_homecoming)	C++14	31 / 100	296 ms	8764 KiB

homecoming

#include "homecoming.h"
#include <iostream>
using namespace std;
const int nmax=5005;
long long dp[nmax],sum[nmax],sk[nmax],C[nmax];
long long ans,prefmx;
int i,n,rot,k,aux1,aux2;
void solve()
{
    prefmx=0;
    for(i=1;i<=n;i++)
        dp[i]=0;
    for(i=1;i<=n-k+1;i++)
    {
        dp[i]=1LL*max(dp[i],dp[i-1]);
        dp[i+k-1]=1LL*max(sum[i]+prefmx-(sk[i+k-1]-sk[i]),dp[i+k-1]);
        prefmx=1LL*max(prefmx,dp[i]-sum[i]);
    }
    for(i=1;i<=n;i++)
     ans=1LL*max(ans,dp[i]);
}
long long solve(int N, int K, int *A, int *B)
{
    ans=0;
    for(i=0;i<N;i++)
        ans+=1LL*(A[i]-B[i]);
    n=N,k=K;
    for(rot=1;rot<=N;rot++)
    {
        for(i=1;i<=N;i++)
        {
            C[i]=A[i-1]-B[i-1];
            sk[i]=1LL*sk[i-1]+B[i-1];
            sum[i]=1LL*C[i]+sum[i-1];
        }
        solve();
        aux1=A[0];aux2=B[0];
        for(i=0;i<N-1;i++)
            A[i]=A[i+1],B[i]=B[i+1];
        A[N-1]=aux1;B[N-1]=aux2;
    }
    return ans;
}

• Subtask 1: 13 / 13
• Subtask 2: 18 / 18
• Subtask 3: 0 / 31
• Subtask 4: 0 / 38