제출 #1324074

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1324074		sh_qaxxorov_571	JJOOII 2 (JOI20_ho_t2)	C++20	100 / 100	9 ms	1808 KiB

ho_t2

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

/**
 * JOI 2020 Final - JOI-string
 * Vaqt murakkabligi: O(N)
 */
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, K;
    string S;
    cin >> N >> K >> S;

    vector<int> posJ, posO, posI;
    for (int i = 0; i < N; i++) {
        if (S[i] == 'J') posJ.push_back(i);
        else if (S[i] == 'O') posO.push_back(i);
        else if (S[i] == 'I') posI.push_back(i);
    }

    // Agar harflar yetarli bo'lmasa
    if (posJ.size() < K || posO.size() < K || posI.size() < K) {
        cout << -1 << endl;
        return 0;
    }

    int min_op3 = 2e9;

    // Har bir mumkin bo'lgan K ta 'J' blokidan boshlaymiz
    for (int i = 0; i + K <= posJ.size(); i++) {
        int endJ = posJ[i + K - 1];

        // 'J' lardan keyin keladigan birinchi 'O' indeksini topamiz
        auto itO = lower_bound(posO.begin(), posO.end(), endJ);
        int idxO = distance(posO.begin(), itO);
        
        if (idxO + K > posO.size()) continue;
        int endO = posO[idxO + K - 1];

        // 'O' lardan keyin keladigan birinchi 'I' indeksini topamiz
        auto itI = lower_bound(posI.begin(), posI.end(), endO);
        int idxI = distance(posI.begin(), itI);

        if (idxI + K > posI.size()) continue;
        int endI = posI[idxI + K - 1];

        // Umumiy oraliq: [posJ[i], endI]
        // Bu oraliqdagi barcha keraksiz belgilar Op3 orqali o'chiriladi
        int current_total_len = endI - posJ[i] + 1;
        min_op3 = min(min_op3, current_total_len - 3 * K);
    }

    if (min_op3 > N) cout << -1 << endl;
    else cout << min_op3 << endl;

    return 0;
}

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