제출 #1148786

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1148786		dosts	JJOOII 2 (JOI20_ho_t2)	C++20	100 / 100	18 ms	6880 KiB

ho_t2

#include <bits/stdc++.h>
#pragma GCC target("avx2")
#pragma GCC optimize("O3,unroll-loops")
using namespace std;
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " <<    
#define all(cont) cont.begin(),cont.end()
#define vi vector<int>

const int inf = 1e18,N = 3e5+1,MOD = 998244353,B = 250;

void solve() { 
    int n,k;
    cin >> n >> k;
    string s;
    cin >> s;
    vi js(n+1,0),os(n+1,0),is(n+1,0);
    for (int i=1;i<=n;i++) {
        js[i] = js[i-1]+(s[i-1] == 'J');
        os[i] = os[i-1]+(s[i-1] == 'O');
        is[i] = is[i-1]+(s[i-1] == 'I');
    }
    int ans = inf;
    for (int i=1;i<=n;i++) {
        int p = i;
        int l = 1,r = n;
        while (l<=r) {
            int m = (l+r) >> 1;
            if (js[m]-js[p-1] < k) l = m+1;
            else r = m-1;
        }
        if (l > n) continue;
        p = l;
        l = p+1;
        r = n;
        while (l<=r) {
            int m = (l+r) >> 1;
            if (os[m]-os[p-1] < k) l = m+1;
            else r = m-1;
        }
        if (l > n) continue;
        p = l;
        l =  p+1;
        r = n;
        while (l <= r) {
            int m = (l+r) >> 1;
            if (is[m]-is[p-1] < k) l = m+1;
            else r = m-1;
        }
        if (l > n) continue;
        ans = min(ans,l-i+1-3*k);
    }
    if (ans < inf) cout << ans << '\n';
    else cout << -1 << '\n';
}

int32_t main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef Dodi 
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    //cin >> t;
    while (t --> 0) solve();
}

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