Submission #59729

#	Time	Username	Problem	Language	Result	Execution time	Memory
59729		model_code	Homecoming (BOI18_homecoming)	C++17	31 / 100	195 ms	32036 KiB

homecoming

// Andrei-Costin Constantinescu
// O(N) - Dynamic Programming
#include <bits/stdc++.h>
#include "homecoming.h"

using namespace std;

const int NMAX = 2000000;

int N, K;
int A[2 * NMAX + 5]; // Subjects
int B[2 * NMAX + 5]; // Textbooks

typedef long long int lint;
const lint INF = 2E16L;

lint sPartB[2 * NMAX + 5];
inline lint getSPartB(int l, int r) {
    assert(1 <= l && 1 <= r && l <= 2 * N && r <= 2 * N && l <= r);
    return sPartB[r] - sPartB[l - 1];
}

lint taken[NMAX], notTaken[NMAX];
inline void updateDp(lint &where, const lint val) {
    if (val > where)
        where = val;
}

lint computeDp(bool forceFirst) {
    for (int i = 0; i <= N; ++ i)
        taken[i] = notTaken[i] = -INF;

    if (forceFirst)
        taken[1] = A[1] - getSPartB(1, K);
    else
        notTaken[1] = 0;

    lint ans = -INF;
    for (int i = 1; i <= N; ++ i) {
        // notTaken[i] -> taken[i], decrease less if ForceFirst
        if (!forceFirst)
            updateDp(taken[i], notTaken[i] + A[i] - getSPartB(i, i + K - 1));
        else
            updateDp(taken[i], notTaken[i] + A[i] - getSPartB(i, min(N, i + K - 1)));

        updateDp(ans, taken[i]), updateDp(ans, notTaken[i]);

        // taken[i] - B[i + K] + A[i + K] -> taken[i + 1]
        if (i + 1 <= N) {
            if (!forceFirst || i + K <= N)
                updateDp(taken[i + 1], taken[i] - B[i + K] + A[i + 1]);
            else
                updateDp(taken[i + 1], taken[i] + A[i + 1]);
        }

        // taken[i] -> notTaken[i + K];
        if (i + K <= N)
            updateDp(notTaken[i + K], taken[i]);

        // notTaken[i] -> notTaken[i + 1]
        if (i + 1 <= N)
            updateDp(notTaken[i + 1], notTaken[i]);

    }
    if (ans < 0)
        return 0;
    else
        return ans;
}

lint solve(int n, int k, int a[], int b[]) {
    N = n, K = k;
    assert(1 <= N && 1 <= K && N < NMAX && K <= N);

    for (int i = 1; i <= N; ++ i) {
        A[i] = a[i - 1];
        A[N + i] = A[i];
    }
    for (int i = 1; i <= N; ++ i) {
        B[i] = b[i - 1];
        B[N + i] = B[i];
    }
    for (int i = 1; i <= 2 * N; ++ i)
        sPartB[i] = sPartB[i - 1] + B[i];
    return max(computeDp(false), computeDp(true));
}

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