Submission #201619

#	Time	Username	Problem	Language	Result	Execution time	Memory
201619		waynetuinfor	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	76 ms	3080 KiB

ho_t2

#include <algorithm>
#include <array>
#include <iostream>
#include <string>
#include <vector>

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);
  int n, k;
  std::cin >> n >> k;
  std::string s;
  std::cin >> s;
  for (int i = 0; i < n; ++i) {
    if (s[i] == 'J') {
      s[i] = 0;
    } else if (s[i] == 'O') {
      s[i] = 1;
    } else if (s[i] == 'I') {
      s[i] = 2;
    }
  }
  std::vector<std::array<int, 3>> pref(n + 1, std::array<int, 3>{});
  for (int i = 0; i < n; ++i) {
    pref[i + 1] = pref[i];
    pref[i + 1][s[i]]++;
  }
  int ans = n + 1;
  for (int i = 0; i < n; ++i) {
    bool ok = true;
    int p = i;
    for (int j = 0; j < 3; ++j) {
      int r = n + 1;
      for (int d = 20; d >= 0; --d) {
        if (r - (1 << d) <= p) continue;
        if (pref[r - (1 << d)][j] - pref[p][j] >= k) r -= (1 << d);
      }
      if (r > n) {
        ok = false;
        break;
      }
      p = r;
    }
    if (!ok) break;
    int res = 0;
    for (int j = 0; j < 3; ++j) res += pref[p][j] - pref[i][j] - k;
    ans = std::min(ans, res);
  }
  if (ans == n + 1) ans = -1;
  std::cout << ans << "\n";
  return 0;
}

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