제출 #1343220

#제출 시각아이디문제언어결과실행 시간메모리
1343220maxiedJJOOII 2 (JOI20_ho_t2)C++20
0 / 100
0 ms344 KiB
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

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

    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    int ans = INT_MAX;
    bool ok = false;
    vector<int> pj(n + 1, 0);
    vector<int> po(n + 1, 0);
    vector<int> pi(n + 1, 0);
    for (int i = 0; i < n; i++){
        pj[i + 1] = pj[i] + (s[i] == 'J');
    }
    for (int i = 0; i < n; i++){
        po[i + 1] = po[i] + (s[i] == 'O');
    }
    for (int i = 0; i < n; i++){
        pi[i + 1] = pi[i] + (s[i] == 'I');
    }
    auto sum = [&](vector<int> &p, int l, int r) -> int{
        return p[r + 1] - p[l];
    };
    for (int i = 0; i < n; i++){
        if (s[i] == 'J'){
            // start the joi here
            // get the J
            int l = i;
            int lo = i, hi = n - 1;
            // nnnnnnyyy
            while (lo < hi){
                int mid = (lo + hi) >> 1;
                if (sum(pj, l, mid) >= k){
                    hi = mid;
                }
                else{
                    lo = mid + 1;
                }
            }
            if (sum(pj, l, lo) < k){
                continue;
            }
            l = lo + 1;
            lo = l;
            hi = n - 1;

            //get the O
            while (lo < hi){
                int mid = (lo + hi) >> 1;
                if (sum(po, l, mid) >= k){
                    hi = mid;
                }
                else{
                    lo = mid + 1;
                }
            }
            if (sum(po, l, lo) < k){
                continue;
            }
            l = lo + 1;
            lo = l;
            hi = n - 1;

            //get the I
            while (lo < hi){
                int mid = (lo + hi) >> 1;
                if (sum(pi, l, mid) >= k){
                    hi = mid;
                }
                else{
                    lo = mid + 1;
                }
            }
            if (sum(pi, l, lo) < k){
                continue;
            }

            ok = true;
            ans = min(ans, lo - i + 1 - (k * 3));
        }
    }
    if (!ok){
        cout << "-1" << '\n';
    }
    else{
        cout << ans << '\n';
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...