oj.uz

Submission #78893

# Submission time Handle Problem Language Result Execution time Memory
78893 2018-10-09T13:34:43 Z bogdan10bos Homecoming (BOI18_homecoming) C++14
100 / 100
 231 ms 252588 KB 
#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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 500 KB Output is correct
3 Correct 2 ms 628 KB Output is correct
4 Correct 3 ms 628 KB Output is correct
5 Correct 2 ms 628 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 500 KB Output is correct
3 Correct 2 ms 628 KB Output is correct
4 Correct 3 ms 628 KB Output is correct
5 Correct 2 ms 628 KB Output is correct
6 Correct 2 ms 836 KB Output is correct
7 Correct 3 ms 1036 KB Output is correct
8 Correct 3 ms 1192 KB Output is correct
9 Correct 2 ms 1356 KB Output is correct
10 Correct 3 ms 1356 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 16916 KB Output is correct
2 Correct 5 ms 16916 KB Output is correct
3 Correct 188 ms 103964 KB Output is correct
4 Correct 4 ms 103964 KB Output is correct
5 Correct 11 ms 103964 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 500 KB Output is correct
3 Correct 2 ms 628 KB Output is correct
4 Correct 3 ms 628 KB Output is correct
5 Correct 2 ms 628 KB Output is correct
6 Correct 2 ms 836 KB Output is correct
7 Correct 3 ms 1036 KB Output is correct
8 Correct 3 ms 1192 KB Output is correct
9 Correct 2 ms 1356 KB Output is correct
10 Correct 3 ms 1356 KB Output is correct
11 Correct 49 ms 16916 KB Output is correct
12 Correct 5 ms 16916 KB Output is correct
13 Correct 188 ms 103964 KB Output is correct
14 Correct 4 ms 103964 KB Output is correct
15 Correct 11 ms 103964 KB Output is correct
16 Correct 231 ms 145920 KB Output is correct
17 Correct 86 ms 145920 KB Output is correct
18 Correct 157 ms 145920 KB Output is correct
19 Correct 139 ms 198688 KB Output is correct
20 Correct 142 ms 252588 KB Output is correct
21 Correct 141 ms 252588 KB Output is correct