Submission #495338

#TimeUsernameProblemLanguageResultExecution timeMemory
495338600MihneaMonochrome Points (JOI20_monochrome)C++17
35 / 100
2054 ms4564 KiB
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = 400000 + 7;
int n;
string s;


int main() {
  ios::sync_with_stdio(0); cin.tie(0);

  ///freopen ("input", "r", stdin);

  cin >> n >> s;

  vector<int> a, b;
  for (int i = 0; i < 2 * n; i++) {
    if (s[i] != s[0]) {
      a.push_back(i);
    }
    else {
      b.push_back(i);
    }
  }
  vector<ll> cnt(n);

  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (a[i] < b[j]) {
        cnt[(n - i + j) % n] += min(b[j] - a[i] - 1, 2 * (n - 1) - (b[j] - a[i] - 1));
      }
    }
    for (int j = 0; j < n; j++) {
      if (a[i] > b[j]) {
        cnt[(n - i + j) % n] += min(a[i] - b[j] - 1, 2 * (n - 1) - (a[i] - b[j] - 1));
      }
    }
  }
  ll sol = 0;


  for (auto& x : cnt) {
    sol = max(sol, x);
  }
  cout << sol / 2 << "\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...