Submission #628433

#TimeUsernameProblemLanguageResultExecution timeMemory
628433MohamedFaresNebiliMonochrome Points (JOI20_monochrome)C++14
35 / 100
2091 ms8468 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using ld = long double; using pi = pair<pair<int, int>, pair<int, int>>; #define ff first #define ss second #define pb push_back #define all(x) (x).begin(), (x).end() #define lb lower_bound #define int ll int N, ST[80005]; string S; vector<int> A, B; int solve(int v) { vector<pair<int, int>> P; for(int l = 0; l < N; l++) P.push_back({A[l], B[(l + v) % N]}); int res = 0; for(int l = 0; l < N; l++) { for(int i = l + 1; i < N; i++) { int U = P[l].first, V = P[l].second; int X = P[i].first, Y = P[i].second; if(U > V) swap(U, V); if(X > Y) swap(X, Y); if(V < X) continue; if(Y < U) continue; if(U > X && V < Y) continue; if(X > U && Y < V) continue; res++; } } return res; } int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> N >> S; int res = 0; for(int l = 0; l < 2 * N; l++) { if(S[l] == 'B') A.push_back(l); if(S[l] == 'W') B.push_back(l); } int lo = 0, hi = N - 1; while(lo <= hi) { int md = (lo + hi) / 2; int U = solve(md), V = solve(md + 1); if(V > U) { lo = md + 1, res = max(res, V); } else hi = md - 1, res = max(res, U); } cout << res << "\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...