Submission #1275003

#TimeUsernameProblemLanguageResultExecution timeMemory
1275003MisterReaperJJOOII 2 (JOI20_ho_t2)C++20
100 / 100
16 ms12388 KiB
// File jjooii2.cpp created on 01.10.2025 at 09:00:10
#include <bits/stdc++.h>

using i64 = long long;

#ifdef DEBUG 
    #include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
    #define debug(...) void(23)
#endif

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int N, K;
    std::cin >> N >> K;

    std::string S;
    std::cin >> S;

    std::vector<int> A(N);
    for (int i = 0; i < N; ++i) {
        if (S[i] == 'J') {
            A[i] = 0;
        } else if (S[i] == 'O') {
            A[i] = 1;
        } else {
            A[i] = 2;
        }
    }

    std::vector<std::vector<int>> pre(N + 1, std::vector<int>(3));
    for (int i = 0; i < N; ++i) {
        pre[i + 1] = pre[i];
        pre[i + 1][A[i]] += 1;
    }

    int ans = N + 1;
    int p0 = 0, p1 = 0, p2 = 0;
    for (int i = 0; i < N; ++i) {
        if (S[i] != 'J') {
            continue;
        }
        while (p0 != N + 1 && pre[p0][0] - pre[i][0] != K) {
            p0++;
        }
        if (p0 == N + 1) {
            break;
        }
        while (p1 != N + 1 && pre[p1][1] - pre[p0][1] != K) {
            p1++;
        }
        if (p1 == N + 1) {
            break;
        }
        while (p2 != N + 1 && pre[p2][2] - pre[p1][2] != K) {
            p2++;
        }
        if (p2 == N + 1) {
            break;
        }
        ans = std::min(ans, p2 - i);
    }

    if (ans == N + 1) {
        std::cout << "-1\n";
    } else {
        std::cout << ans - 3 * K << '\n';
    }

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...