Submission #710653

#	Time	Username	Problem	Language	Result	Execution time	Memory
710653		KoD	Monochrome Points (JOI20_monochrome)	C++17	100 / 100	25 ms	3468 KiB

monochrome

#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

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

    int N;
    cin >> N;
    vector<int> W, B;
    W.reserve(N);
    B.reserve(N);
    for (int i = 0; i < 2 * N; ++i) {
        char c;
        cin >> c;
        (c == 'W' ? W : B).push_back(i);
    }

    vector<ll> coeff(N);
    auto add = [&](int l, int r, int x) {
        while (l < 0) {
            l += N;
            r += N;
        }
        while (l >= N) {
            l -= N;
            r -= N;
        }
        if (r < N) {
            coeff[l] += x;
            coeff[r] -= x;
        } else {
            coeff[l] += x;
            coeff[0] += x;
            coeff[r - N] -= x;
        }
    };

    for (int i = 0, a = 0, b = 0, c = 0; i < N; ++i) {
        while (a < N and W[i] - B[a] > N) a += 1;
        while (b < N and B[b] < W[i]) b += 1;
        while (c < N and B[c] - W[i] < N) c += 1;
        add(0 - i, a - i, 2 * N);
        add(c - i, N - i, 2 * N);
        add(0 - i, a - i, -W[i]);
        add(a - i, b - i, +W[i]);
        add(b - i, c - i, -W[i]);
        add(c - i, N - i, +W[i]);
    }
    for (int i = 0, a = 0, b = 0, c = 0; i < N; ++i) {
        while (a < N and B[i] - W[a] >= N) a += 1;
        while (b < N and W[b] <= B[i]) b += 1;
        while (c < N and W[c] - B[i] <= N) c += 1;
        add(i - a + 1, i - 0 + 1, -B[i]);
        add(i - b + 1, i - a + 1, +B[i]);
        add(i - c + 1, i - b + 1, -B[i]);
        add(i - N + 1, i - c + 1, +B[i]);
    }

    for (int i = 1; i < N; ++i) {
        coeff[i] += coeff[i - 1];
    }
    cout << (*max_element(begin(coeff), end(coeff)) - N) / 2 << '\n';

    return 0;
}

• Subtask 1: 4 / 4
• Subtask 2: 21 / 21
• Subtask 3: 10 / 10
• Subtask 4: 65 / 65