Submission #540940

#	Time	Username	Problem	Language	Result	Execution time	Memory
540940		Cookie197	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	14 ms	2076 KiB

ho_t2

#include<iostream>
#include<vector>
#include<set>
#include<algorithm>
using namespace std;

#define ll long long
#define mp make_pair
#define endl "\n"
#define out(x) cout<< #x << " = " << x << endl

int n,k,J,O,I;
string s;
vector<int> v[3];
signed main(){
    cin>>n>>k>>s;
    v[0].push_back(0); v[1].push_back(0); v[2].push_back(0);
    for (int i=0;i<n;i++){
        if (s[i] == 'J') v[0].push_back(i+1), J++;
        if (s[i] == 'O') v[1].push_back(i+1), O++;
        if (s[i] == 'I') v[2].push_back(i+1), I++;
    }

    int ans = 1e9;
    for (int i=k;i<=J;i++){
        int opos = lower_bound(v[1].begin(),v[1].end(),v[0][i]) - v[1].begin();
        
        if (opos + k - 1 > O) continue;
        int oend = v[1][opos + k - 1];
        
        int ipos = lower_bound(v[2].begin(),v[2].end(),oend) - v[2].begin();
        if (ipos + k - 1 > I) continue;
        int iend = v[2][ipos + k - 1];
        
        ans = min(ans, iend - v[0][i-k+1] + 1 - k*3);
    }
    cout<<(ans == 1e9 ? -1 : ans)<<endl;
    
}

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