Submission #201460

#	Time	Username	Problem	Language	Result	Execution time	Memory
201460		Alexa2001	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	18 ms	3064 KiB

ho_t2

#include <bits/stdc++.h>

using namespace std;

const int Nmax = 2e5 + 5;

int sI[Nmax], sJ[Nmax], sO[Nmax], N, K;
char a[Nmax];

int main()
{
  //  freopen("input", "r", stdin);
    cin.sync_with_stdio(false); cin.tie(0);

    cin >> N >> K;
    cin >> (a+1);
    
    int s, i, j, k, ans = 1e9;
    
    for(i=1; i<=N; ++i) sJ[i] = sJ[i-1] + (a[i] == 'J');
    for(i=1; i<=N; ++i) sO[i] = sO[i-1] + (a[i] == 'O');
    for(i=1; i<=N; ++i) sI[i] = sI[i-1] + (a[i] == 'I');

    i = j = k = 0;
    for(s=0; s<N; ++s)
    {
        while(i <= N && sJ[i] - sJ[s] < K) ++i;
        while(j <= N && sO[j] - sO[i] < K) ++j;
        while(k <= N && sI[k] - sI[j] < K) ++k;

        if(i <= N && j <= N && k <= N && k - s < ans) 
            ans = k - s;
    }
    
    ans -= 3 * K;
    if(ans > N) ans = -1;
    cout << ans << '\n';

    return 0;
}

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