Submission #1181399

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181399		peteza	JJOOII 2 (JOI20_ho_t2)	C++20	100 / 100	7 ms	6612 KiB

ho_t2

#include <bits/stdc++.h>
using namespace std;

int n, k;
int cmin = INT_MAX;
string str;

int firstpos[3][300005];
int qs[3][300005];

int ord(char x) {
    if(x == 'J') return 0;
    if(x == 'O') return 1;
    return 2;
}

int main() {
    memset(firstpos, -1, sizeof firstpos);
    cin.tie(0) -> sync_with_stdio(0);
    cin >> n >> k;
    cin >> str;
    for(int i=1;i<=n;i++) {
        for(int k=0;k<3;k++) qs[k][i] = qs[k][i-1];
        qs[ord(str[i-1])][i]++;
    }
    for(int i=n;i>=1;i--) {
        for(int k=0;k<3;k++) {
            firstpos[k][qs[k][i]] = i;
        }
    }
    for(int i=0;i<=n;i++) {
        int cpos = i;
        for(int j=0;j<3;j++) {
            cpos = (firstpos[j][qs[j][cpos] + k]);
            if(cpos == -1) break;
        }
        if(cpos != -1) cmin = min(cmin, cpos - i);
    }
    cout << (cmin > n ? -1 : cmin - k*3);
}

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