제출 #1333514

#제출 시각아이디문제언어결과실행 시간메모리
1333514lywoemJJOOII 2 (JOI20_ho_t2)C++20
100 / 100
9 ms3016 KiB
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define l(a, b, i) for (ll i = a; i < b; i++)
#define rl(a, b, i) for (ll i = a; i >= b; i--)
#define vpair vector<pair<ll, ll>>
#define inf LLONG_MAX
#define ninf LLONG_MIN

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ll N, K; string S; cin >> N >> K >> S;

    vector<ll> posJ, posO, posI;
    posJ.push_back(0); posO.push_back(0); posI.push_back(0);

    l(0, N, i) {
        if (S[i] == 'J') posJ.push_back(i);
        else if (S[i] == 'O') posO.push_back(i);
        else posI.push_back(i);
    }

    ll ans = inf;
    ll sz = posJ.size();
    l(1, sz - K + 1, i) {
        ll l = posJ[i]; // idx đầu tiên của J
        ll r = posJ[i + K - 1]; // idx J thứ k-th, tính từ cái idx đầu tiên

        auto itO = upper_bound(posO.begin() + 1, posO.end(), r);
        if (itO == posO.end()) continue;

        ll idxO = itO - posO.begin();
        if (idxO + K - 1 >= posO.size()) continue;
        ll rO = posO[idxO + K -1]; // idx O thứ k-th

        auto itI = upper_bound(posI.begin() + 1, posI.end(), rO);
        if (itI == posI.end()) continue;

        ll idxI = itI - posI.begin();
        if (idxI + K - 1 >= posI.size()) continue;
        ll rI = posI[idxI + K -1]; // idx I thứ k-th

        ans = min(ans, rI - l + 1 - 3 * K);
    }

    if (ans == inf) cout << -1;
    else cout << ans;

}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...