Submission #297804

#TimeUsernameProblemLanguageResultExecution timeMemory
297804balbitJJOOII 2 (JOI20_ho_t2)C++14
100 / 100
11 ms2180 KiB
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<int, int>
#define f first
#define s second

#define pb push_back
#define SZ(x) (int)((x).size())
#define ALL(x) (x).begin(), (x).end()
#define MX(a,b) a=max(a,b)
#ifdef BALBIT
#define bug(...) cerr<<"#"<<#__VA_ARGS__<<": ", _do(__VA_ARGS__)
template<typename T> void _do(T && x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S&&...y){cerr<<x<<", "; _do(y...);}
#define IOS()
#else
#define IOS() ios::sync_with_stdio(0), cin.tie(0)
#define endl '\n'
#define bug(...)
#endif // BALBIT

void GG(){cout<<-1<<endl; exit(0);}

const int maxn = 3e5+5;
int n,k; string s;

signed main(){
    IOS();
    bug(1,2);
    cin>>n>>k;
    cin>>s;
    array<vector<int> ,3> kk;
    for (int i = 0; i<n; ++i) {
        if (s[i] == 'J') kk[0].pb(i);
        if (s[i] == 'O') kk[1].pb(i);
        if (s[i] == 'I') kk[2].pb(i);
    }
    int mnl = 10000000;
    for (int i = 0; i<SZ(kk[0])-k+1; ++i) {
        int to = kk[0][i+k-1];
        int tmp = upper_bound(ALL(kk[1]), to) - kk[1].begin();
        if (tmp + k-1 < SZ(kk[1])) {
            to = kk[1][tmp+k-1];
        }else continue;

        tmp = upper_bound(ALL(kk[2]), to) - kk[2].begin();
        if (tmp + k-1 < SZ(kk[2])) {
            to = kk[2][tmp+k-1];
        }else continue;

        mnl = min(mnl, to - kk[0][i] + 1);
    }
    if (mnl > n) GG();
    cout<<mnl - k*3<<endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...