oj.uz

Submission #64142

# Submission time Handle Problem Language Result Execution time Memory
64142 2018-08-03T12:05:38 Z Bodo171 Homecoming (BOI18_homecoming) C++14
31 / 100
 296 ms 8764 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]);
}
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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 2 ms 412 KB Output is correct
4 Correct 4 ms 488 KB Output is correct
5 Correct 3 ms 632 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 2 ms 412 KB Output is correct
4 Correct 4 ms 488 KB Output is correct
5 Correct 3 ms 632 KB Output is correct
6 Correct 207 ms 772 KB Output is correct
7 Correct 240 ms 796 KB Output is correct
8 Correct 90 ms 796 KB Output is correct
9 Correct 296 ms 796 KB Output is correct
10 Correct 4 ms 796 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 43 ms 8764 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 376 KB Output is correct
3 Correct 2 ms 412 KB Output is correct
4 Correct 4 ms 488 KB Output is correct
5 Correct 3 ms 632 KB Output is correct
6 Correct 207 ms 772 KB Output is correct
7 Correct 240 ms 796 KB Output is correct
8 Correct 90 ms 796 KB Output is correct
9 Correct 296 ms 796 KB Output is correct
10 Correct 4 ms 796 KB Output is correct
11 Runtime error 43 ms 8764 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Halted 0 ms 0 KB -