oj.uz

Submission #60702

# Submission time Handle Problem Language Result Execution time Memory
60702 2018-07-24T14:36:48 Z SpaimaCarpatilor Homecoming (BOI18_homecoming) C++17
100 / 100
 288 ms 119360 KB 
#include "homecoming.h"
#include<bits/stdc++.h>

using namespace std;

const long long INF = 1LL << 60;
int K, *A, *B;
long long *sB, x[2000009], y[2000009];

long long getSB (int i, int j)
{
    if (i > j) return 0;
    if (i == 0) return sB[j];
    return sB[j] - sB[i - 1];
}

long long solve (int N, int kk, int *aa, int *bb)
{
    A = new int[2 * N], B = new int[2 * N];
    sB = new long long[2 * N], K = kk;
    for (int i=0; i<N; i++)
        A[i] = A[N + i] = aa[i], B[i] = B[N + i] = bb[i];
    sB[0] = B[0];
    for (int i=1; i<2 * N; i++)
        sB[i] = sB[i - 1] + B[i];
    long long ans = 0;
    for (int i=0; i<N; i++)
        ans += A[i] - B[i];
    ans = max (ans, 0LL);
    if (N == K)
        return ans;
    x[0] = -INF, y[0] = 0;
    for (int i=1; i<N; i++)
    {
        x[i] = max (x[i - 1] + A[i] - B[i + K - 1], y[i - 1] + A[i] - getSB (i, i + K - 1));
        y[i] = max (x[i - 1], y[i - 1]);
    }
    ans = max (ans, max (x[N - 1], y[N - 1]));
    x[0] = A[0] - getSB (0, K - 1);
    y[0] = -INF;
    for (int i=1; i<N; i++)
    {
        long long c0 = (i + K - 1 >= N ? 0 : B[i + K - 1]);
        int l = i, r = min (i + K - 1, N - 1);
        long long c1 = getSB (l, r);
        x[i] = max (x[i - 1] + A[i] - c0, y[i - 1] + A[i] - c1);
        y[i] = max (x[i - 1], y[i - 1]);
    }
    ans = max (ans, max (x[N - 1], y[N - 1]));
    return ans;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 380 KB Output is correct
2 Correct 3 ms 488 KB Output is correct
3 Correct 3 ms 564 KB Output is correct
4 Correct 3 ms 564 KB Output is correct
5 Correct 3 ms 564 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 380 KB Output is correct
2 Correct 3 ms 488 KB Output is correct
3 Correct 3 ms 564 KB Output is correct
4 Correct 3 ms 564 KB Output is correct
5 Correct 3 ms 564 KB Output is correct
6 Correct 3 ms 792 KB Output is correct
7 Correct 3 ms 848 KB Output is correct
8 Correct 3 ms 848 KB Output is correct
9 Correct 4 ms 848 KB Output is correct
10 Correct 4 ms 848 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 28008 KB Output is correct
2 Correct 7 ms 28008 KB Output is correct
3 Correct 288 ms 110148 KB Output is correct
4 Correct 5 ms 110148 KB Output is correct
5 Correct 14 ms 110148 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 380 KB Output is correct
2 Correct 3 ms 488 KB Output is correct
3 Correct 3 ms 564 KB Output is correct
4 Correct 3 ms 564 KB Output is correct
5 Correct 3 ms 564 KB Output is correct
6 Correct 3 ms 792 KB Output is correct
7 Correct 3 ms 848 KB Output is correct
8 Correct 3 ms 848 KB Output is correct
9 Correct 4 ms 848 KB Output is correct
10 Correct 4 ms 848 KB Output is correct
11 Correct 66 ms 28008 KB Output is correct
12 Correct 7 ms 28008 KB Output is correct
13 Correct 288 ms 110148 KB Output is correct
14 Correct 5 ms 110148 KB Output is correct
15 Correct 14 ms 110148 KB Output is correct
16 Correct 286 ms 110180 KB Output is correct
17 Correct 125 ms 110180 KB Output is correct
18 Correct 257 ms 110180 KB Output is correct
19 Correct 199 ms 110180 KB Output is correct
20 Correct 180 ms 119360 KB Output is correct
21 Correct 198 ms 119360 KB Output is correct