Submission #60702

#	Time	Username	Problem	Language	Result	Execution time	Memory
60702		SpaimaCarpatilor	Homecoming (BOI18_homecoming)	C++17	100 / 100	288 ms	119360 KiB

homecoming

#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 / 13
• Subtask 2: 18 / 18
• Subtask 3: 31 / 31
• Subtask 4: 38 / 38