Submission #1281289

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281289		dhuyyyy	JJOOII 2 (JOI20_ho_t2)	C++20	100 / 100	18 ms	5492 KiB

ho_t2

#include<bits/stdc++.h>
#define fi first
#define se second
#define int long long
using namespace std;

using ll = long long;
using ii = pair<int, int>;
using aa = array<int,3>;

const int N = 1e6+5;

int n, k, ans = 1e18;

int pre[3][N];

string s;

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    cin >> n >> k >> s;
    while (!s.empty() && s.back() != 'I') s.pop_back();
    reverse(s.begin(),s.end());
    while (!s.empty() && s.back() != 'J') s.pop_back();
    reverse(s.begin(),s.end());
    if ((int)s.size() == 0) return cout << -1,0;
    n = (int)s.size();
    s = ' ' + s;
    for (int i = 1; i <= n; i++){
        for (int j = 0; j <= 2; j++){
            pre[j][i] = pre[j][i-1];
        }
        if (s[i] == 'J') pre[0][i]++;
        if (s[i] == 'O') pre[1][i]++;
        if (s[i] == 'I') pre[2][i]++;
    }
    for (int i = 1; i <= n; i++){
        int J = lower_bound(pre[0] + 1,pre[0] + 1 + n,pre[0][i-1] + k) - pre[0];
        int O = lower_bound(pre[1] + J,pre[1] + 1 + n,pre[1][J] + k) - pre[1];
        int I = lower_bound(pre[2] + O,pre[2] + 1 + n,pre[2][O] + k) - pre[2];
        if (max({J,O,I}) <= n){
            ans = min(ans,I-i+1-k*3);
        }
    }
    cout << (ans == (int)1e18 ? -1 : ans);
    return 0;
}

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