제출 #1368343

#제출 시각아이디문제언어결과실행 시간메모리
1368343edoJJOOII 2 (JOI20_ho_t2)C++20
100 / 100
10 ms3792 KiB
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, k;
  string s;
  cin >> n >> k >> s;

  auto get_val = [](char& c) {
    if(c == 'J') return 0;
    if(c == 'O') return 1;
    return 2;
  };
  vector pref(3, vector<int>(n + 1));
  for(int i = 0; i < n; ++i) {
    for(int c = 0; c < 3; ++c) {
      pref[c][i + 1] = pref[c][i];
    }
    pref[get_val(s[i])][i + 1]++;
  }

  if(min({pref[0][n], pref[1][n], pref[2][n]}) < k) {
    cout << -1;
    return 0;
  }

  auto chk = [&](int c, int l, int r) {
    return pref[c][r + 1] - pref[c][l];
  };

  auto nxt = [&](int c, int l, int need) {
    int lo = l, hi = n - 1, ans = n;
    while(lo <= hi) {
      int mid = (lo + hi) >> 1;
      if(chk(c, l, mid) >= need) {
        hi = mid - 1;
        ans = mid;
      } else {
        lo = mid + 1;
      }
    }
    return ans;
  };

  const int inf = 1 << 30;
  int ans = inf;
  for(int l = 0; l < n; ++l) {
    if(s[l] != 'J') continue;
    int en = nxt(0, l, k);
    if(en == n) continue;
    int en2 = nxt(1, en + 1, k);
    if(en2 == n) continue;
    int en3 = nxt(2, en2 + 1, k);
    if(en3 == n) continue;
    ans = min(ans, en3 - l + 1 - 3 * k);
  }

  cout << (ans == inf ? -1 : ans);

  return 0;
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…