Submission #955154

#	Time	Username	Problem	Language	Result	Execution time	Memory
955154		ililog	JJOOII 2 (JOI20_ho_t2)	C++11	100 / 100	6 ms	3304 KiB

ho_t2

using namespace std;
#include<iostream>
#include<fstream>

int vj[200001], vo[200001], vi[200001];
int lj, lo, li;
int n, k;
string s;

int main() {
    cin >> n >> k;
    cin >> s;
    for (int i = 0; i<n; i++) {
        if (s[i] == 'J') {
            vj[++lj] = i;
        } else if (s[i] == 'O') {
            vo[++lo] = i;
        } else {
            vi[++li] = i;
        }
    }
    
    int pj = 1, po = 1, pi = 1, minim = n+1;
    while (pj + k - 1 <= lj && po + k - 1 <= lo && pi + k - 1 <= li) {
        while (po + k - 1 <= lo && vo[po] <= vj[pj+k-1]) po++;
        
        if (po + k - 1 <= lo) {
            while (pi + k - 1 <= li && vi[pi] <= vo[po+k-1]) pi++;
            
            if (pj + k - 1 <= lj && po + k - 1 <= lo && pi + k - 1 <= li) {
                int st = vj[pj];
                int dr = vi[pi+k-1];
                minim = min(minim, dr-st+1-3*k);
            }
        }
        pj++;
    }
    
    if (minim == n+1) {
        cout << "-1";
    } else {
        cout << minim;
    }
    
    return 0;
}

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