Submission #298152

#TimeUsernameProblemLanguageResultExecution timeMemory
298152eriksuenderhaufMonochrome Points (JOI20_monochrome)C++17
35 / 100
1998 ms5908 KiB
#pragma GCC optimize("O3") //#pragma GCC optimize("unroll-loops") //#pragma GCC target("avx2") #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 2e5 + 5; int a[4*N]; ll dp[N]; int ord[2*N]; ll solve(int n, int i) { i = ord[i]; int ptr[2] = {i+n, i+n}, cnt[4] = {0, 0, 0, 0}; // auto next = [&](int& j) { // j = j+1 < 2*n ? j+1 : j+1-2*n; // }; // #define next(x) x = x+1 < 2*n ? x+1 : x+1-2*n ll val = 0; for (int j = i, c = a[i]; j < i+n; c = a[++j]) { while (a[ptr[c]++] == c) cnt[c+2]++; val += min(cnt[c+2], cnt[c^1]) + cnt[c]++; } return val; } mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int main() { ios_base::sync_with_stdio(false); cin.tie(0); auto cur_t = clock(); int n; cin >> n; string s; cin >> s; for (int i = 0; i < 2*n; i++) a[i] = a[i+2*n] = s[i] == 'B', ord[i] = i; shuffle(ord, ord+n, rng); ll ans = 0; int i = 0; while (clock() - cur_t < 1993000) ans = max(ans, i < n ? solve(n, i++) : 0); cout << ans << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...