Submission #787240

#	Time	Username	Problem	Language	Result	Execution time	Memory
787240		tvladm2009	JJOOII 2 (JOI20_ho_t2)	C++17	0 / 100	1 ms	212 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 low = 1, high = n, sol = -1;
  while (low <= high) {
    int mid = (low + high) / 2;
    if (getcost(mid) == INF) {
      high = mid - 1;
    } else {
      if (getcost(mid) <= getcost(mid - 1)) {
        sol = mid;
        low = mid + 1;
      } else {
        high = mid - 1;
      }
    }
  }
  if (sol == -1) {
    cout << "-1";
    return 0;
  }
  cout << getcost(sol) << "\n";
  return 0;
}

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