Submission #495322

#TimeUsernameProblemLanguageResultExecution timeMemory
495322600MihneaMonochrome Points (JOI20_monochrome)C++17
25 / 100
2086 ms332 KiB
#include <iostream>
#include <vector>
#include <string>
#include <functional>
#include <cassert>

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);

  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);

  ll sol = 0;
  for (int shift = 0; shift < n; shift++) {
    for (int i = 0; i < n; i++) {
      int i2 = (i + shift) % n, l = min(a[i], b[i2]), r = max(a[i], b[i2]);
      for (int j = 0; j < n; j++) {
        int j2 = (j + shift) % n;
        if (l < min(a[j], b[j2]) && min(a[j], b[j2]) < r && r < max(a[j], b[j2])) {
          cnt[shift]++;
        }
      }
    }
  }


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