Submission #482910

#	Time	Username	Problem	Language	Result	Execution time	Memory
482910		cristi_a	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	10 ms	3152 KiB

ho_t2

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

const int nmax = 2e5 + 5;

int sj[nmax],so[nmax],si[nmax];

int main () {
  int n,k; cin >> n >> k;
  string t; cin >> t;
  t = "X" + t;
  for(int i=1; i<=n; i++) {
    sj[i] = sj[i-1] + (t[i]=='J');
    so[i] = so[i-1] + (t[i]=='O');
    si[i] = si[i-1] + (t[i]=='I');
  }
  int j = 0;
  int o = 0;
  int i = 0;
  int mn = 1e9;
  for(int l=0; l<n; l++) {
    while(j<=n and sj[j]-sj[l]<k) j++;
    while(o<=n and so[o]-so[j]<k) o++;
    while(i<=n and si[i]-si[o]<k) i++;

    if(j<=n and o<=n and i<=n and i-l<mn)
      mn = i - l;
  }
  mn = mn - 3*k;
  if(mn>n) mn = -1;
  cout << mn;
  return 0;
}

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