Submission #1034492

#	Time	Username	Problem	Language	Result	Execution time	Memory
1034492		nguyendinhanh1508	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	13 ms	5608 KiB

ho_t2

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define mx 1000007
#define inf LLONG_MAX/20
#define pi pair<int, int>
#define mp make_pair

int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  int n, k;
  cin >> n >> k;
  string s;
  cin >> s;
  int J[n];
  int O[n];
  int I[n];
  J[0] = 0;
  O[0] = 0;
  I[0] = 0;
  if(s[0] == 'J') J[0]++;
  else if(s[0] == 'O') O[0]++;
  else if(s[0] == 'I') I[0]++;
  for(int i = 1; i < n; i++){
    J[i] = J[i - 1];
    O[i] = O[i - 1];
    I[i] = I[i - 1];
    if(s[i] == 'J') J[i]++;
    else if(s[i] == 'O') O[i]++;
    else if(s[i] == 'I') I[i]++;
  }
  int ans = inf;
  for(int i = 0; i < n; i++){
    int prevJ = 0;
    if(i != 0) prevJ = J[i - 1];  
    if(s[i] != 'J') continue;
    int jay = lower_bound(J + i, J + n, k + prevJ) - J;
    if(jay == n) continue;
    int oou = lower_bound(O + jay + 1, O + n, k + O[jay]) - O;
    if(oou == n) continue;
    int aii = lower_bound(I + oou + 1, I + n, k + I[oou]) - I;
    if(aii == n) continue;
    int cost = (aii - i + 1) - (3 * k);
    ans = min(cost, ans); 
  }
  if(ans == inf) ans = -1;
  cout << ans;
  return 0; 
}

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