Submission #1089389

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089389		Andrei_ierdnA	Homecoming (BOI18_homecoming)	C++17	100 / 100	164 ms	196440 KiB

homecoming

#include "homecoming.h"
#include <iostream>

using namespace std;

using ll = long long;

const int MAXN = 2000000;
ll INF = 10000000000000000LL;

struct DpVector
{
    ll a, b;
    static const DpVector id;
};
const DpVector DpVector::id = {0, -INF};

struct DpMatrix
{
    ll a, b, c, d;
    /// f({x, y}) = {max(x+a, y+b), max(x+c, y+d)}
    /// ( a b )
    /// ( c d )
    static const DpMatrix id;
    static void mult(const DpMatrix &a, const DpMatrix &b, DpMatrix &c)
    {
        c.a = max(a.a + b.a, a.b + b.c);
        c.b = max(a.a + b.b, a.b + b.d);
        c.c = max(a.c + b.a, a.d + b.c);
        c.d = max(a.c + b.b, a.d + b.d);
    }
    static void mult(const DpMatrix &a, const DpVector &b, DpVector &c)
    {
        c.a = max(a.a + b.a, a.b + b.b);
        c.b = max(a.c + b.a, a.d + b.b);
    }
};
const DpMatrix DpMatrix::id = {0, -INF, -INF, 0};

int n, k;
int *a, *b;
ll sb[MAXN+2];
DpMatrix pref[MAXN+2], suf[MAXN+2], auxmat;
DpVector auxvec[2];

void calcSb()
{
    sb[0] = 0;
    for (int i = 0; i < k; i++) {
        sb[0] += b[i];
    }
    for (int i = 1; i < n; i++) {
        sb[i] = sb[i-1] - b[i-1] + b[(i+k-1)%n];
    }
}

void calcPrefMats()
{
    pref[0] = {0, 0, a[0]-sb[0], a[0]-b[k-1]};
    for (int i = 1; i < n; i++) {
        auxmat.c = a[i] - sb[i];
        auxmat.d = a[i] - b[(i+k-1)%n];
        DpMatrix::mult(auxmat, pref[i-1], pref[i]);
    }
}

void calcSufMats()
{
    suf[n-1] = {0, 0, a[n-1]-sb[n-1], a[n-1]-b[(n+k-2)%n]};
    for (int i = n-2; i >= 0; i--) {
        auxmat.c = a[i] - sb[i];
        auxmat.d = a[i] - b[(i+k-1)%n];
        DpMatrix::mult(suf[i+1], auxmat, suf[i]);
    }
}

long long getSimpleAns()
{
    long long ans = 0;
    for (int i = 0; i < n; i++) {
        ans = ans + a[i] - b[i];
    }
    return max(ans, 0LL);
}

long long solve(int nn, int kk, int *aa, int *bb)
{
    n = nn;
    k = kk;
    a = aa;
    b = bb;
    calcSb();
    calcPrefMats();
    calcSufMats();
    long long ans = getSimpleAns();
    DpMatrix::mult(pref[n-1], DpVector::id, auxvec[0]);
    ans = max(ans, max(auxvec[0].a, auxvec[0].b));
    for (int i = 1; i < n; i++) {
        DpMatrix::mult(suf[i], DpVector::id, auxvec[0]);
        DpMatrix::mult(pref[i-1], auxvec[0], auxvec[1]);
        ans = max(ans, max(auxvec[1].a, auxvec[1].b));
    }
    return ans;
}

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