Submission #889524

#TimeUsernameProblemLanguageResultExecution timeMemory
889524MilosMilutinovicMonochrome Points (JOI20_monochrome)C++14
0 / 100
0 ms348 KiB
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; string s; cin >> s; string t = ""; for (int i = 0; i < 2 * n; i++) { if (s[i] == 'B') { for (int j = 0; j < 2 * n; j++) { t += s[(i + j) % (2 * n)]; } break; } } s = t; vector<int> a; vector<int> b; for (int i = 0; i < 2 * n; i++) { if (s[i] == 'B') { a.push_back(i); } else { b.push_back(i); } } vector<int> fenw(2 * n); auto Modify = [&](int x, int v) { while (x < 2 * n) { fenw[x] += v; x |= (x + 1); } }; auto Query = [&](int x) { int v = 0; while (x >= 0) { v += fenw[x]; x = ((x & (x + 1))) - 1; } return v; }; auto GetSum = [&](int L, int R) { return Query(R) - Query(L - 1); }; auto Solve = [&](int k) { vector<vector<array<int, 3>>> qs(2 * n); vector<int> to(2 * n, -1); for (int i = 0; i < n; i++) { int L = a[i]; int R = b[(i + k) % n]; to[L] = R; if (L <= R) { if (L != 0) { qs[L - 1].push_back({0, L - 1, -1}); qs[L - 1].push_back({R + 1, 2 * n - 1, -1}); } qs[R].push_back({0, L - 1, +1}); qs[R].push_back({R + 1, 2 * n - 1, +1}); } else { swap(L, R); qs[L].push_back({L + 1, R - 1, +1}); qs[R - 1].push_back({L + 1, R - 1, -1}); qs[2 * n - 1].push_back({L + 1, R - 1, +1}); } } fenw = vector<int>(2 * n, 0); long long ret = 0; for (int i = 0; i < 2 * n; i++) { for (auto& p : qs[i]) { if (p[0] <= p[1]) { ret += GetSum(p[0], p[1]) * p[2]; } } if (to[i] != -1) { Modify(to[i], 1); } } return ret; }; long long ans = 0; for (int i = 0; i < n; i++) { ans = max(ans, Solve(i)); } cout << ans << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...