Submission #536380

#	Time	Username	Problem	Language	Result	Execution time	Memory
536380		Monarchuwu	Monochrome Points (JOI20_monochrome)	C++17	35 / 100	2072 ms	3540 KiB

monochrome

#include<iostream>
#include<algorithm>
#include<vector>
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll;

const int N = 2e5 + 8;
int n, n2;
char s[N << 2];

char c[N << 1];
int solve(int l, int r) {
    copy(s + l, s + r + 1, c + 1);

    vector<int> vec[2];
    for (int i = n; i; --i)
        vec[c[i] == 'W'].push_back(i);

    int sum(0);
    for (int i = n + 1, x, y, p; i <= n2; ++i) {
        x = c[i] == 'B';
        y = vec[x].back(); vec[x].pop_back();

        sum += vec[x].size();
        sum += lower_bound(all(vec[x ^ 1]), y, greater<int>()) - vec[x ^ 1].begin();
    }
    return sum;
}

int main() {
    cin.tie(NULL)->sync_with_stdio(false);
    cin >> n >> (s + 1);
    n2 = n << 1;
    copy(s + 1, s + n2 + 1, s + n2 + 1);

    int ans(0);
    for (int i = 1; i <= n; ++i)
        ans = max(ans, solve(i, i + n2 - 1));
    cout << ans << '\n';
}
/**  /\_/\
 *  (= ._.)
 *  / >0  \>1
**/

Compilation message (stderr)

monochrome.cpp: In function 'int solve(int, int)':
monochrome.cpp:21:31: warning: unused variable 'p' [-Wunused-variable]
   21 |     for (int i = n + 1, x, y, p; i <= n2; ++i) {
      |                               ^

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