Submission #201852

#	Time	Username	Problem	Language	Result	Execution time	Memory
201852		nvmdava	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	13 ms	1416 KiB

ho_t2

#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define ll long long
#define ff first
#define ss second
#define N 200002
#define MOD 1000000007

string s;
int a[N];
int cnt[3];

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

    int n, k;
    cin>>n>>k;
    cin>>s;
    for(int i = 0; i < n; ++i){
        if(s[i] == 'J')
            a[i] = 0;
        else if(s[i] == 'O')
            a[i] = 1;
        else
            a[i] = 2;
    }

    int i1 = 0, i2, i3;
    while(i1 < n && cnt[0] < k)
        if(a[i1++] == 0)
            ++cnt[0];
    i2 = i1;
    while(i2 < n && cnt[1] < k)
        if(a[i2++] == 1)
            ++cnt[1];
    i3 = i2;
    while(i3 < n && cnt[2] < k)
        if(a[i3++] == 2)
            ++cnt[2];
    if(cnt[2] < k){
        cout<<-1;
        return 0;
    }
    int ans = i3 - 3 * k;
    for(int i = 0; i < n; ++i){
        if(a[i] == 0)
            --cnt[0];
        while(i1 < n && cnt[0] < k){
            if(a[i1] == 0)
                ++cnt[0];
            else if(a[i1] == 1)
                --cnt[1];
            ++i1;
        }
        while(i2 < n && cnt[1] < k){
            if(a[i2] == 1)
                ++cnt[1];
            else if(a[i2] == 2)
                --cnt[2];
            ++i2;
        }
        while(i3 < n && cnt[2] < k){
            if(a[i3] == 2)
                ++cnt[2];
            ++i3;
        }
        if(cnt[2] == k && cnt[1] == k && cnt[0] == k)
            ans = min(ans, i3 - 3 * k - i - 1);
    }
    cout<<ans;
}

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