제출 #1174317

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

const int inf = 1e9;

vector<int> po, jp, ip;
vector<pair<int, int>> J, I;
int n, k;
string s;

int solve(){
    int ans = inf;
    for (auto [il, ir] : I){
        while (!J.empty()){
            if (po[il] - po[J.back().second] >= k){
                ans = min(ans, il - 2*k - J.back().first);
                break;
            }
            else{
                J.pop_back();
            }
        }
        if (J.empty()){
            return ans;
        }
    }

    return ans;
}


int main () {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n >> k >> s;
    po.resize(n+1, 0);

    for (int i=0; i<n; i++){
        if (s[i] == 'J'){
            jp.push_back(i+1);
            po[i+1] = po[i];
        }
        else if (s[i] == 'I'){
            ip.push_back(i+1);
            po[i+1] = po[i];
        }
        else{
            po[i+1] = po[i]+1;
        }
    }

    for (int l=0, r=l+k-1; r<jp.size(); l++, r++){
        J.push_back({jp[l], jp[r]});
    }

    for (int l=0, r=l+k-1; r<ip.size(); l++, r++){
        I.push_back({ip[l], ip[r]});
    }
    
    reverse(J.begin(), J.end());
    reverse(I.begin(), I.end());

    int ans = solve();
    if (ans == inf) cout << "-1\n";
    else cout << ans << '\n';
    
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...