Submission #1205676

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205676		AIF_is_carving	Colouring a rectangle (eJOI19_colouring)	C++20	20 / 100	58 ms	17764 KiB

colouring

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

void solve() {
    LL n, m;
    cin >> n >> m;
    vector<LL> a(n + m - 1), b(n + m - 1);
    LL sum = 0;
    for (LL i = 0; i < n + m - 1; i++) {
        cin >> a[i];
        sum += a[i];
    }
    for (LL i = 0; i < n + m - 1; i++) {
        cin >> b[i];
        sum += b[i];
    }

    // Special case: 1×M or N×1 grid
    if (n == 1 || m == 1) {
        LL total = 0;
        for (LL i = 0; i < n; i++) {
            for (LL j = 0; j < m; j++) {
                LL d1 = i - j + (m - 1);  // index into a
                LL d2 = i + j;            // index into b
                total += min(a[d1], b[d2]);
            }
        }
        cout << total << "\n";
        return;
    }

    // Build padded diagonal arrays Ax, Bx
    LL diff = llabs(n - m);
    LL L   = max(n, m);
    vector<LL> Ax, Bx;
    if (n >= m) {
        // pad A in front, append a[], pad B at back
        Ax.insert(Ax.end(), diff, 0);
        Ax.insert(Ax.end(), a.begin(), a.end());
        Bx.insert(Bx.end(), b.begin(), b.end());
        Bx.insert(Bx.end(), diff, 0);
    } else {
        // n < m: pad A at back, pad B in front
        Ax.insert(Ax.end(), a.begin(), a.end());
        Ax.insert(Ax.end(), diff, 0);
        Bx.insert(Bx.end(), diff, 0);
        Bx.insert(Bx.end(), b.begin(), b.end());
    }

    // Helper to compute the "mex" contribution on a given parity
    auto compute_mex = [&](bool take_even_indices){
        vector<LL> U, V;
        for (LL i = 0; i < (LL)Ax.size(); i++) {
            if ((i % 2 == 0) == take_even_indices) U.push_back(Ax[i]);
            if ((i % 2 == 0) == (L % 2 == 1 ? take_even_indices : !take_even_indices))
                V.push_back(Bx[i]);
        }
        if (U.size() < V.size()) swap(U, V);
        LL k = U.size() / 2;
        // fold pairs from ends
        for (LL i = 0; i < k; i++) {
            U[i] += U[U.size() - 1 - i];
        }
        for (LL i = 0; i < (LL)V.size() / 2; i++) {
            V[i] += V[V.size() - 1 - i];
        }
        // prefix sums
        for (LL i = 1; i <= k; i++) {
            U[i] += U[i - 1];
            V[i] += V[i - 1];
        }
        // insert zero at front for alignment
        U.insert(U.begin(), 0);
        V.insert(V.begin(), 0);

        LL best = 0;
        for (LL i = 0; i <= k; i++) {
            best = max(best, U[i] + V[k - i]);
        }
        return best;
    };

    LL mex1 = compute_mex(true);
    LL mex2 = compute_mex(false);

    cout << (sum - mex1 - mex2) << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // single test case
    solve();
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 20
• Subtask 5: 10 / 10
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20