Submission #60662

#	Time	Username	Problem	Language	Result	Execution time	Memory
60662		SpaimaCarpatilor	Homecoming (BOI18_homecoming)	C++17	0 / 100	376 ms	85740 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;

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

void combine (long long ans[2][2], long long dp1[2][2], long long dp2[2][2])
{
    for (int i=0; i<2; i++)
        for (int j=0; j<2; j++)
            ans[i][j] = min (dp1[i][0] + dp2[0][j], dp1[i][1] + dp2[1][j]);
}

long long dp[8000009][2][2];
void build (int nod, int st, int dr)
{
    if (st == dr)
    {
        dp[nod][1][0] = dp[nod][0][0] = 0;
        dp[nod][1][1] = A[st] - B[st + K - 1];
        dp[nod][0][1] = A[st] - getSB (st, st + K - 1);
        return ;
    }
    int mij = (st + dr) >> 1, f1 = nod << 1, f2 = f1 | 1;
    build (f1, st, mij);
    build (f2, mij + 1, dr);
    combine (dp[nod], dp[f1], dp[f2]);
}

long long ansQ[2][2];
void getQuery (int nod, int st, int dr, int x, int y)
{
    if (x <= st && dr <= y)
    {
        if (x == st) memcpy (ansQ, dp[nod], sizeof (dp[nod]));
        else
        {
            long long aux[2][2];
            memcpy (aux, ansQ, sizeof (ansQ));
            combine (ansQ, aux, dp[nod]);
        }
        return ;
    }
    int mij = (st + dr) >> 1, f1 = nod << 1, f2 = f1 | 1;
    if (x <= mij) getQuery (f1, st, mij, x, y);
    if (mij < y) getQuery (f2, mij + 1, dr, x, y);
}

long long solve (int N, int kk, int *aa, int *bb)
{
    if (N == 1) return max (0LL, (long long) aa[0] - bb[0]);
    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;
    build (1, 1, N - 1 + N - K);
    for (int i=0; i<N; i++)
    {
        ///assume this one is free
        getQuery (1, 1, N - 1 + N - K, i + 1, i + N - K);
        long long curr = max (ansQ[0][0], ansQ[0][1]);
        if (curr > ans)
            ans = curr;
    }
    return ans;
}

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