Submission #60654

#	Time	Username	Problem	Language	Result	Execution time	Memory
60654		SpaimaCarpatilor	Homecoming (BOI18_homecoming)	C++17	31 / 100	1077 ms	28028 KiB

homecoming

#include "homecoming.h"
#include<bits/stdc++.h>

using namespace std;

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

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

long long solve (int N, int K, int *aa, int *bb)
{
    A = new int[2 * N], B = new int[2 * N];
    sB = new long long[2 * N];
    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];
    for (int i=0; i<N; i++)
    {
        ///assume this one is free
        x[i] = -INF, y[i] = 0;
        int lst = i + N - K;
        for (int j=i + 1; j<=lst; j++)
        {
            x[j] = max (x[j - 1] + A[j] - B[j + K - 1], y[j - 1] + A[j] - getSB (j, j + K - 1));
            y[j] = max (x[j - 1], y[j - 1]);
        }
        long long curr = max (x[lst], y[lst]);
        if (curr > ans)
            ans = curr;
    }
    return ans;
}

• Subtask 1: 13 / 13
• Subtask 2: 18 / 18
• Subtask 3: 0 / 31
• Subtask 4: 0 / 38