Submission #1298936

#TimeUsernameProblemLanguageResultExecution timeMemory
1298936MasterMoonJJOOII 2 (JOI20_ho_t2)C++20
100 / 100
7 ms2316 KiB
#include <bits/stdc++.h>
using namespace std;
#define __Master_Moon__ int main()
#define ll long long
#define el "\n"
#define base 300
#define fi first
#define sq(x) (x)*(x) 
#define se second   
#define pub push_back  
#define puf push_front
#define pii pair <int, int>
#define pll pair <long long, long long>
#define piii pair <long long, pair <int, int>> 
#define iiii pair <int, pair <int, pair <int, int>>>
#define plll pair <long long, pair <long long, long long>>
#define FOR(i, a, b) for(int i = (a);i <=(b);i++)
#define FO(i, a, b) for(int i = (a);i >= (b);i--)
#define REP(i, n) for(int i = 0;i < (n);i++)
long const maxn = 2e5 + 5;
int p[maxn][2],n,k,ans = INT_MAX;
string s;
void solve() 
{
    cin >> n >> k >> s;
    s = ' ' + s;
    int j = 1,cnt = 0;
    memset(p,-1,sizeof p); 
    FOR(i,1,n)
    {
        if(s[i] == 'J') cnt++;
        while(cnt >= k)
        {
            if(s[j] == 'J') 
            {
                cnt--;
                if(cnt < k)
                {
                    cnt++;
                    break;
                }
            }
            j++;
        }
        if(cnt >= k) p[i][0] = j;
    }
    j = 1;
    cnt = 0;
    FOR(i,1,n)
    {
        if(s[i] == 'O') cnt++;
        while(cnt >= k)
        {
            if(s[j] == 'O') 
            {
                cnt--;
                if(cnt < k)
                {
                    cnt++;
                    break;
                }
            }
            j++;
        }
        if(cnt >= k && p[j-1][0] != -1) p[i][1] = p[j-1][0];
    }
    j = 1;
    cnt = 0;
    FOR(i,1,n)
    {
        if(s[i] == 'I') cnt++;
        while(cnt >= k)
        {
            if(s[j] == 'I') 
            {
                cnt--;
                if(cnt < k)
                {
                    cnt++;
                    break;
                }
            }
            j++;
        }
        if(cnt >= k && p[j-1][1] != -1) ans = min(ans,i-p[j-1][1]-3*k+1);
    }
    if(ans == INT_MAX) ans = -1;
    cout << ans;
} 
__Master_Moon__
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...