Submission #1283230

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283230		hoangtien69	JJOOII 2 (JOI20_ho_t2)	C++20	100 / 100	31 ms	5396 KiB

ho_t2

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 5;
#define int long long

int n, k;
string s;
int pre[MAXN][3];
int ans = INT_MAX;

int findd(int t, int pos)
{
    int l = pos;
    int r = n;
    int ans = -1;
    while(l <= r)
    {
        int m = (l + r) / 2;
        if (pre[m][t] - pre[pos - 1][t] >= k)
        {
            ans = m;
            r = m - 1;
        }
        else
        {
            l = m + 1;
        }
    }
    return ans;
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> k;
    cin >> s;
    s = "%" + s;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j <= 2; j++)
        {
            pre[i][j] = pre[i - 1][j];
        }
        if (s[i] == 'J')
        {
            pre[i][0]++;
        }
        else if (s[i] == 'O')
        {
            pre[i][1]++;
        }
        else if (s[i] == 'I')
        {
            pre[i][2]++;
        }
    }
    for (int i = 1; i <= n; i++)
    {
        int l = i;
        int cur = i;
        int nxt = findd(0, cur);
        if (nxt == -1)
        {
            continue;
        }
        cur = nxt + 1;
        nxt = findd(1, cur);
        if (nxt == -1)
        {
            continue;
        }
        cur = nxt + 1;
        nxt = findd(2, cur);
        if (nxt == -1)
        {
            continue;
        }
        int r = nxt;
        ans = min(ans, r - l + 1 - 3 * k);
    }
    if (ans == INT_MAX)
    {
        cout << -1;
    }
    else
    {
        cout << ans;
    }
}

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