Submission #495335

#	Time	Username	Problem	Language	Result	Execution time	Memory
495335		600Mihnea	Monochrome Points (JOI20_monochrome)	C++17	35 / 100	2029 ms	4504 KiB

monochrome

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

  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 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]);
      int inside = r - l - 1;
      int outside = 2 * n - inside - 2;
      cnt[shift] += min(inside, outside);
    }
  }
  ll sol = 0;


  for (auto& x : cnt) {
    sol = max(sol, x);
  }
  cout << sol / 2 << "\n";
}

• Subtask 1: 4 / 4
• Subtask 2: 21 / 21
• Subtask 3: 10 / 10
• Subtask 4: 0 / 65