Submission #938066

#	Time	Username	Problem	Language	Result	Execution time	Memory
938066		Andrey	JJOOII 2 (JOI20_ho_t2)	C++14	100 / 100	7 ms	4120 KiB

ho_t2

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

string s;
vector<int> bruh(200001);

int n,k;
int haha[200001][3];

void calc(int a) {
    int y = 0,br = 0;
    for(int i = 0; i < n; i++) {
        if(bruh[i] == a) {
            br++;
        }
        while(bruh[y] != a || br > k) {
            if(bruh[y] == a) {
                br--;
            }
            y++;
        }
        if(br >= k) {
            haha[i][a] = y;
        }
        else {
            haha[i][a] = -1;
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> k;
    cin >> s;
    for(int i = 0; i < n; i++) {
        if(s[i] == 'J') {
            bruh[i] = 0;
        }
        else if(s[i] == 'O') {
            bruh[i] = 1;
        }
        else {
            bruh[i] = 2;
        }
    }
    calc(0);
    calc(1);
    calc(2);
    int ans = INT_MAX;
    for(int i = 0; i < n; i++) {
        int c = i;
        c = haha[c][2];
        if(c == -1) {
            continue;
        }
        c = haha[c][1];
        if(c == -1) {
            continue;
        }
        c = haha[c][0];
        if(c == -1) {
            continue;
        }
        ans = min(ans,abs(i-c)+1);
    }
    if(ans == INT_MAX) {
        cout << -1;
    }
    else {
        cout << ans-3*k;
    }
    return 0;
}

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