Submission #1194103

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194103		miniob	JJOOII 2 (JOI20_ho_t2)	C++20	100 / 100	14 ms	1564 KiB

ho_t2

#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;
}

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