Submission #1345099

#TimeUsernameProblemLanguageResultExecution timeMemory
1345099thaibaotran555JJOOII 2 (JOI20_ho_t2)C++20
0 / 100
0 ms344 KiB
///TRAN THAI BAO :3

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <deque>

using namespace std;

#define maxN 200007

int n, k;
string s;
int a[maxN] = {0};
int goTo[maxN][3] = {0};

void xuLy(int ty)
{
    deque<int>q;
    for(int i = 0; i <= n; i++)
    {
        if(a[i] == ty)
            q.push_back(i);
        while(q.size() > k)
            q.pop_front();
        if(q.size() < k)
            goTo[i][ty] = -1;
        else goTo[i][ty] = q.front();
    }
}

void solve()
{
    cin >> n >> k >> s;
    s = ' ' + s;
    a[0] = -1;
    for(int i = 1; i <= n; i++)
        if(s[i] == 'J')
            a[i] = 0;
        else if(s[i] == 'O')
            a[i] = 1;
        else a[i] = 2;
    for(int i = 0; i < 3; i++)
        xuLy(i);
    int ans = 2*n;
    for(int i = 0; i <= n; i++)
    {
        int cur = i;
        for(int j = 2; j >= 0; j--)
        {
            cur = goTo[cur][j]-1;
            if(cur == -1)
                break;
        }
        if(cur == -1)
            continue;
        ans = min(ans, i - cur - 3*k);
    }
    if(ans == 2*n)
        cout << -1;
    else cout << ans;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...