제출 #653129

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
653129		pauloamed	JJOOII 2 (JOI20_ho_t2)	C++14	100 / 100	58 ms	3316 KiB

ho_t2

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 200010;

int J[MAXN], O[MAXN], I[MAXN];
int N, K;
string s;

int bb(int v[], int x){
  // achar ultimo cara i, v[i] < x
  if(v[0] >= x) return 0;
  int ans = 0;
  int pot = (1 << 30);
  while(pot){
    int mans = ans + pot;
    if(mans < N && v[mans] < x) ans = mans;
    pot /= 2;
  }
  if(ans + 1 == N) return -1;
  else return ans + 1;
}

int solveI(int i){
  if(i == N) return -1;
  int prev = I[i - 1];

  int nxt = bb(I, prev + K);
  if(nxt == -1) return -1;
  int cost = (nxt - i + 1) - K;
  return cost;
}

int solveO(int i){
  if(i == N) return -1;
  int prev = O[i - 1];

  int nxt = bb(O, prev + K);
  if(nxt == -1) return -1;
  int cost = (nxt - i + 1) - K;
  int x; 
  if((x = solveI(nxt + 1)) == -1) return -1;
  return cost + x;
}

int solveJ(int i){ // starting from i
  int prev = 0;
  if(i > 0) prev = J[i - 1];

  int nxt = bb(J, prev + K);
  if(nxt == -1) return -1;
  int cost = (nxt - i + 1) - K;
  int x; 
  if((x = solveO(nxt + 1)) == -1) return -1;
  return cost + x;
}

int32_t main(){
  cin.tie(NULL)->sync_with_stdio(false);
  cin >> N >> K;
  cin >> s;

  for(int i = 0; i < N; ++i){
    J[i] = (s[i] == 'J');
    O[i] = (s[i] == 'O');
    I[i] = (s[i] == 'I');
    if(i){
      J[i] += J[i - 1];
      O[i] += O[i - 1];
      I[i] += I[i - 1];
    }
  }

  int ans = INT_MAX;
  for(int i = 0; i < N; ++i){
    int x = solveJ(i);
    if(x == -1) break;
    // cout << i << " " << x << "\n";
    ans = min(ans, x);
  }
  cout << ((ans == INT_MAX)? -1 : ans) << "\n";
}

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