제출 #1194103

#제출 시각아이디문제언어결과실행 시간메모리
1194103miniobJJOOII 2 (JOI20_ho_t2)C++20
100 / 100
14 ms1564 KiB
#include <bits/stdc++.h>
using namespace std;

int jp[200007];
int op[200007];
int ip[200007];

int main()
{
    int n, k;
    string s;
    cin >> n >> k >> s;
    int jc = 0, oc = 0, ic = 0;
    for(int i = 1; i <= n; i++)
    {
        if(s[i - 1] == 'J')
        {
        	jc++;
            jp[jc] = i;
        }
        else if(s[i - 1] == 'O')
        {
        	oc++;
            op[oc] = i;
        }
        else if(s[i - 1] == 'I')
        {
        	ic++;
            ip[ic] = i;
        }
    }
    if(jc < k || oc < k || ic < k)
    {
        cout << -1 << endl;
        return 0;
    }
    int ans = INT_MAX;
    for(int i = 1; i + k - 1 <= jc; i++)
    {
        if(int(lower_bound(op + 1, op + oc + 1, jp[i + k - 1] + 1) - op) > oc - k + 1)
        {
        	break;
        }
        if(lower_bound(ip + 1, ip + ic + 1, op[lower_bound(op + 1, op + oc + 1, jp[i + k - 1] + 1) - op + k - 1] + 1) - ip > ic - k + 1)
        {
        	break;
        }
        ans = min(ans, ip[int(lower_bound(ip + 1, ip + ic + 1, op[lower_bound(op + 1, op + oc + 1, jp[i + k - 1] + 1) - op + k - 1] + 1) - ip) + k - 1] - jp[i] + 1 - 3 * k);
    }
    if(ans == INT_MAX)
    {
    	cout << -1 << endl;
    }
    else
    {
    	cout << ans << endl;
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...