Submission #1174321

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174321		lxz20071231	JJOOII 2 (JOI20_ho_t2)	C++20	100 / 100	5 ms	3924 KiB

ho_t2

#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, ir-J.back().first + 1 - 3*k);
                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;
}

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