oj.uz

Submission #78885

# Submission time Handle Problem Language Result Execution time Memory
78885 2018-10-09T13:13:50 Z bogdan10bos Homecoming (BOI18_homecoming) C++14
0 / 100
 47 ms 15996 KB 
#include <bits/stdc++.h>

using namespace std;

//#define FILE_IO

typedef long long LL;

LL s[2000005];
LL dp[2000005][2];

int sum(int st, int dr)
{
    if(st == 0) return s[dr];
    return s[dr] - s[st - 1];
}

LL solve(int N, int K, int *A, int *B)
{
    s[0] = B[0];
    LL ans = A[0] - B[0];
    for(int i = 1; i < N; i++)
    {
        s[i] = s[i - 1] + B[i];
        ans += A[i]; ans -= B[i];
    }

    if(N == K)  return ans;

    dp[0][0] = 0LL;
    dp[0][1] = -(1LL << 60);
    for(int i = 1; i < N; i++)
    {
        dp[i][0] = max(dp[i - 1][1], dp[i - 1][0]);
        if(i + K - 1 >= N)   dp[i][1] = max(dp[i - 1][1] + A[i] - B[K - N + i - 1], dp[i - 1][0] + A[i] - sum(i, N - 1) - sum(0, K - N + i - 1));
        else    dp[i][1] = max(dp[i - 1][1] + A[i] - B[i + K - 1], dp[i - 1][0] + A[i] - sum(i, i + K - 1));
    }
    ans = max({ans, dp[N - 1][0], dp[N - 1][1]});

    dp[0][0] = -(1LL << 60);
    dp[0][1] = A[0] - sum(0, K - 1);
    for(int i = 1; i < N; i++)
    {
        dp[i][0] = max(dp[i - 1][1], dp[i - 1][0]);
        if(i + K - 1 >= N)   dp[i][1] = max(dp[i - 1][1] + A[i], dp[i - 1][0] + A[i] - sum(i, N - 1));
        else    dp[i][1] = max(dp[i - 1][1] + A[i] - B[i + K - 1], dp[i - 1][0] + A[i] - sum(i, i + K - 1));
    }
    ans = max({ans, dp[N - 1][0], dp[N - 1][1]});

    return ans;
}

#ifdef FILE_IO
int main()
{

    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);

    int N, K;
    int A[2000005], B[2000005];
    scanf("%d%d", &N, &K);
    for(int i = 0; i < N; i++)  scanf("%d", &A[i]);
    for(int i = 0; i < N; i++)  scanf("%d", &B[i]);

    LL ans = solve(N, K, A, B);
    printf("%lld\n", ans);

    return 0;
}
#endif

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 47 ms 15996 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -