oj.uz

Submission #64129

# Submission time Handle Problem Language Result Execution time Memory
64129 2018-08-03T11:49:53 Z Bodo171 Homecoming (BOI18_homecoming) C++14
0 / 100
 59 ms 8792 KB 
#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]);
    if(dp[n]>ans) ans=1LL*dp[n];
}
long long solve(int N, int K, int *A, int *B)
{
    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;
}

Compilation message

homecoming.cpp: In function 'long long int solve(int, int, int*, int*)':
homecoming.cpp:25:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for(i=0;i<N;i++)
     ^~~
homecoming.cpp:27:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
         n=N,k=K;
         ^

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 5 ms 488 KB Output is correct
3 Incorrect 3 ms 524 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 5 ms 488 KB Output is correct
3 Incorrect 3 ms 524 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 59 ms 8792 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 5 ms 488 KB Output is correct
3 Incorrect 3 ms 524 KB Output isn't correct
4 Halted 0 ms 0 KB -