Submission #956181

#	Time	Username	Problem	Language	Result	Execution time	Memory
956181		samvar_0907	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	10 ms	3364 KiB

ho_t2

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

int main() {

    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    int positions[n][3];
    string opt = "JOI";

    for (int i = 0; i < 3; i++) {
        int leftPointer = 0, rightPointer = 0, count = 0;
        if (s[0] == opt[i]){
            count++;
        }
        while (leftPointer < n) {
            while (count < k && rightPointer < n) {
                rightPointer++;
                if (rightPointer == n){
                    break;;
                }
                if (s[rightPointer] == opt[i]){
                    count++;
                }
            }
            if (count < k) {
                positions[leftPointer][i] = INT_MAX;
                leftPointer++;
                continue;
            }
            positions[leftPointer][i] = rightPointer;
            if (s[leftPointer] == opt[i]){
                count--;
            }
            leftPointer++;
        }
    }

    int ans = INT_MAX;
    for (int i = 0; i < n; i++) {
        int leftPointer = i, rightPointer = positions[i][0];
        for (int j = 1; j < 3; j++) {
            if (rightPointer == INT_MAX){
                continue;
            }
            rightPointer = positions[rightPointer][j];
        }
        ans = min(ans, rightPointer - leftPointer + 1 - 3 * k);
    }
    if (ans > n)
        cout << -1;
    else
        cout << ans;
}

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