Submission #201909

#	Time	Username	Problem	Language	Result	Execution time	Memory
201909		Osama_Alkhodairy	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	47 ms	5248 KiB

ho_t2

#include <bits/stdc++.h>
using namespace std;
#define finish(x) return cout << x << endl, 0
#define ll long long

int n, k;
string s;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> k >> s;
    set <int> p;
    vector <int> J(n);
    for(int i = 0 ; i < n ; i++){
        if(s[i] == 'J') p.insert(i);
        if((int)p.size() > k) p.erase(p.begin());
        if((int)p.size() < k) J[i] = -1;
        else J[i] = *p.begin();
    }
    p.clear();
    vector <int> I(n);
    for(int i = n - 1 ; i >= 0 ; i--){
        if(s[i] == 'I') p.insert(i);
        if((int)p.size() > k) p.erase(--p.end());
        if((int)p.size() < k) I[i] = -1;
        else I[i] = *p.rbegin();
    }
    p.clear();
    int ans = 1e9;
    for(int i = n - 1 ; i >= 0 ; i--){
        if(s[i] == 'O') p.insert(i);
        if((int)p.size() > k) p.erase(--p.end());
        if((int)p.size() < k) continue;
        if(i > 0 && J[i - 1] != -1 && *p.rbegin() + 1 < n && I[*p.rbegin() + 1] != -1){
            ans = min(ans, I[*p.rbegin() + 1] - J[i - 1] + 1);
        }
    }
    if(ans == 1e9) ans = -1;
    else ans -= 3 * k;
    cout << ans << endl;
}

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