Submission #1163033

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163033		tw20000807	JJOOII 2 (JOI20_ho_t2)	C++20	100 / 100	9 ms	3208 KiB

ho_t2

#include<bits/stdc++.h>
#define int long long
#define all(v) v.begin(), v.end()
#define SZ(x) (int)x.size()
#define pii pair<int, int>
#define X first
#define Y second

using namespace std;
const int maxn = 2e5 + 10;
const int mod = 1e9 + 7;//    998244353;
const int llmx = 1e18;

void sol(){
    int n, k;
    cin >> n >> k;
    string s; cin >> s;
    s = " " + s;
    vector< vector< int > > cnt(3);
    for(int i = 1; i <= n; ++i){
        cnt[s[i] == 'J' ? 0 : s[i] == 'O' ? 1 : 2].push_back(i);
    }
    int ans = llmx;
    auto chk = [&](int l, int r) -> void {
        int L = upper_bound(all(cnt[0]), l) - cnt[0].begin() - k;
        int R = lower_bound(all(cnt[2]), r) - cnt[2].begin() + k - 1;
        if(L < 0 || R >= SZ(cnt[2])) return;
        ans = min(ans, n - (cnt[0][L] - 1 + (n - cnt[2][R])) - 3 * k);
    };
    for(int i = 0; i + k - 1 < SZ(cnt[1]); ++i){
        chk(cnt[1][i], cnt[1][i + k - 1]);
    }
    if(ans == llmx) cout << "-1\n";
    else cout << ans << "\n";
}
/*
10 2
OJIJOIOIIJ

2


9 3
JJJOOOIII

0

9 1
IIIOOOJJJ

-1

*/
signed main(){
    ios::sync_with_stdio(0), cin.tie(0), cerr.tie(0);
    int t = 1; //cin >> t;
    while(t--) sol();
}

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