Submission #679127

#TimeUsernameProblemLanguageResultExecution timeMemory
679127Nahian9696JJOOII 2 (JOI20_ho_t2)C++17
100 / 100
14 ms3176 KiB
#include <bits/stdc++.h>
using namespace std;
typedef long long lli;

#define f0(i,n) for(int32_t i = 0; i <  (n); i++)
#define f1(i,n) for(int32_t i = 1; i <= (n); i++)

#define inp(n) lli n; cin >> n
#define inparr(arr,n) lli arr[n]; f0(t_ind, n) cin >> arr[t_ind]

#define all(x) (x).begin(), (x).end()

int main () {
    inp(n);
    inp(k);

    string s;
    cin >> s;

    int nextkthJ[n];
    int nextkthO[n];
    int nextkthI[n];

    memset(nextkthJ, -1, sizeof(nextkthJ));
    memset(nextkthO, -1, sizeof(nextkthO));
    memset(nextkthI, -1, sizeof(nextkthI));

    int l=0, r=0, cnt = 0;

    while (r < n) {
        if (s[r] == 'J') {
            cnt++;
        }
        if (cnt == k) {
            while(s[l] != 'J') {
                nextkthJ[l] = r;
                l++;
            }
            nextkthJ[l] = r;
            l++;
            cnt--;
        }
        r++;
    }
    
    l=0, r=0, cnt = 0;

    while (r < n) {
        if (s[r] == 'O') {
            cnt++;
        }
        if (cnt == k) {
            while(s[l] != 'O') {
                nextkthO[l] = r;
                l++;
            }
            nextkthO[l] = r;
            l++;
            cnt--;
        }
        r++;
    }

    l=0, r=0, cnt = 0;

    while (r < n) {
        if (s[r] == 'I') {
            cnt++;
        }
        if (cnt == k) {
            while(s[l] != 'I') {
                nextkthI[l] = r;
                l++;
            }
            nextkthI[l] = r;
            l++;
            cnt--;
        }
        r++;
    }


    lli ans = 1e9;
    f0(i, n) {
        if(nextkthJ[i] == -1) break;
        if(nextkthO[nextkthJ[i]] == -1) break;
        if(nextkthI[nextkthO[nextkthJ[i]]] == -1) break;

        ans = min(ans, (lli)nextkthI[nextkthO[nextkthJ[i]]] - i + 1);

    }

    if(ans == 1e9) cout << -1 << endl;
    else cout << ans - 3*k << endl;

    return 0;


}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...