제출 #1348619

#제출 시각아이디문제언어결과실행 시간메모리
1348619nathlol2JJOOII 2 (JOI20_ho_t2)C++20
100 / 100
4 ms2324 KiB
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n, k, pf[N], sf[N];
string s;

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n >> k >> s;
    s = " " + s;
    deque<int> dq;
    memset(pf, -1, sizeof pf); memset(sf, -1, sizeof sf);
    for(int i = 1;i<=n;i++){
        if(s[i] == 'J') dq.push_front(i);
        while(dq.size() > k) dq.pop_back();
        if(dq.size() == k) pf[i] = dq.back();
    }
    while(dq.size()) dq.pop_back();
    for(int i = n;i>=1;i--){
        if(s[i] == 'I') dq.push_front(i);
        while(dq.size() > k) dq.pop_back();
        if(dq.size() == k) sf[i] = dq.back();
    }
    while(dq.size()) dq.pop_back();
    int ans = INT_MAX;
    for(int i = 1;i<=n;i++){
        if(s[i] == 'O') dq.push_front(i);
        while(dq.size() > k) dq.pop_back();
        if(dq.size() == k && pf[dq.back() - 1] != -1 && sf[i + 1] != -1){
            ans = min(ans, sf[i + 1] - pf[dq.back() - 1] + 1 - 3 * k);
        }
    }
    cout << (ans == INT_MAX ? -1 : ans);
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...