Submission #787242

#	Time	Username	Problem	Language	Result	Execution time	Memory
787242		tvladm2009	JJOOII 2 (JOI20_ho_t2)	C++17	0 / 100	1 ms	468 KiB

ho_t2

#include <bits/stdc++.h>

using namespace std;

const int INF = (int) 1e9;

int cnt[3];
int n, k;
string s;

int getcost(int x) {
  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;
  int sol = INF;
  int changes = 0;
  for (int i = 1; i <= n; i++) {
    if (getcost(i) == INF) {
      break;
    }
    if (i == 1) {
      continue;
    }
    changes += (getcost(i) > getcost(i - 1));
    sol = min(sol, getcost(i));
  }
  assert(changes <= 1);
  if (sol == INF) {
    cout << "-1";
    return 0;
  }
  cout << sol << "\n";
  return 0;
}

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