Submission #720961

#	Time	Username	Problem	Language	Result	Execution time	Memory
720961		joelgun14	Monochrome Points (JOI20_monochrome)	C++17	35 / 100	2055 ms	9180 KiB

monochrome

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    vector<int> b, w;
    for(int i = 0; i < 2 * n; ++i) {
        if(s[i] == 'B')
            b.push_back(i + 1);
        else
            w.push_back(i + 1);
    }
    int prefb[4 * n + 1], prefw[4 * n + 1];
    memset(prefb, 0, sizeof(prefb));
    memset(prefw, 0, sizeof(prefw));
    //cout << "TEST" << endl;
    for(int i = 1; i <= 2 * n; ++i) {
        prefb[i] = prefb[i - 1];
        prefw[i] = prefw[i - 1];
        if(binary_search(b.begin(), b.end(), i))
            prefb[i]++;
        else
            prefw[i]++;
    }
    //cout << "PREF BUILD DONE" << endl;
    //cout << b.size() << " " << w.size() << endl;
    long long ans = 0;
    for(int i = 0; i < n; ++i) {
        // match b[i] dan w[i]
        long long res = 0;
        for(int j = 0; j < n; ++j) {
            int l = b[j], r = w[(i + j) % n];
            //cout << l << " " << r << endl;
            // cari antara l dan r
            // kalo misal r < l, maka + 2 * n
            if(r < l)
                swap(l, r);
            // pref[2 * n] - pref[r] + pref[l] buat seg 1
            // pref[r] - pref[l] buat seg 2
            int b1 = prefb[2 * n] - prefb[r] + prefb[l - 1], w1 = prefw[2 * n] - prefw[r] + prefw[l - 1];
            int b2 = prefb[r - 1] - prefb[l], w2 = prefw[r - 1] - prefw[l];
            //cout << b1 << " " << b2 << " " << w1 << " " << w2 << endl;
            res += min(b1, w2) + min(b2, w1);
        }
        //cout << res << " " << endl;
        ans = max(ans, res);
    }
    //cout << endl;
    cout << ans / 2 << endl;
}

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