Submission #78893

#	Time	Username	Problem	Language	Result	Execution time	Memory
78893		bogdan10bos	Homecoming (BOI18_homecoming)	C++14	100 / 100	231 ms	252588 KiB

homecoming

#include <bits/stdc++.h>

using namespace std;

//#define FILE_IO

typedef long long LL;

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

LL 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];
    }

    ans = max(ans, 0LL);
    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: 13 / 13
• Subtask 2: 18 / 18
• Subtask 3: 31 / 31
• Subtask 4: 38 / 38