Submission #787243

#	Time	Username	Problem	Language	Result	Execution time	Memory
787243		tvladm2009	JJOOII 2 (JOI20_ho_t2)	C++17	13 / 100	2079 ms	2972 KiB

ho_t2

#include <bits/stdc++.h>

using namespace std;

const int N = (int) 2e5 + 7;
const int INF = (int) 1e9;

int cnt[3], J[N], O[N], I[N];
int n, k;
string s;

int getcost(int x) {
  if (J[x] < k || O[x] < k || I[x] < k) {
    return INF;
  }
  cnt[0] = cnt[1] = cnt[2] = 0;
  int cost = 0;
  while (x <= n) {
    int where = -1;
    if (s[x] == 'J') {
      where = 0;
    } else if (s[x] == 'O') {
      where = 1;
    } else {
      where = 2;
    }
    int mn = INF;
    for (int i = where - 1; i >= 0; i--) {
      mn = min(mn, cnt[i]);
    }
    if (mn < k || cnt[where] == k) {
      cost++;
    } else {
      cnt[where]++;
    }
    if (cnt[0] == k && cnt[1] == k && cnt[2] == k) {
      break;
    }
    x++;
  }
  if (cnt[0] != k || cnt[1] != k || cnt[2] != k) {
    cost = INF;
  }
  return cost;
}

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

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

  cin >> n >> k >> s;
  s = "#" + s;
  for (int i = n; i >= 1; i--) {
    J[i] = J[i + 1];
    O[i] = O[i + 1];
    I[i] = I[i + 1];
    if (s[i] == 'J') {
      J[i]++;
    } else if (s[i] == 'O') {
      O[i]++;
    } else {
      I[i]++;
    }
  }
  int sol = INF;
  for (int i = 1; i <= n; i++) {
    int x = getcost(i);
    if (x == INF) {
      break;
    }
    sol = min(sol, x);
  }
  if (sol == INF) {
    cout << "-1";
    return 0;
  }
  cout << sol << "\n";
  return 0;
}

• Subtask 1: 1 / 1
• Subtask 2: 12 / 12
• Subtask 3: 0 / 87