제출 #1146628

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1146628		koukirocks	JJOOII 2 (JOI20_ho_t2)	C++20	100 / 100	6 ms	2388 KiB

ho_t2

#include <bits/stdc++.h>
#define speed ios_base::sync_with_stdio(0); cin.tie(0)
#define all(x) (x).begin(),(x).end()
#define F first
#define S second

using namespace std;
const int INF=0x3f3f3f3f;

int main() {
    speed;
    int n,k;
    string s;
    cin>>n>>k;
    cin>>s;
    s='-'+s;
    vector<int> dp(n+1);
    int l=1;
    int cnt=0;
    dp[0]=INF;
    for (int i=1;i<=n;i++) {
        cnt+=(s[i]=='J');
        while (cnt-(s[l]=='J')>=k) {
            cnt-=(s[l]=='J');
            l++;
        }
        if (cnt==k) dp[i]=i-l+1-k;
        else dp[i]=INF;
        // cout<<dp[i]<<" ";
    }
    // cout<<"\n";
    l=1;
    cnt=0;
    vector<int> dp2(n+1);
    dp2[0]=INF;
    for (int i=1;i<=n;i++) {
        cnt+=(s[i]=='O');
        while (cnt-(s[l]=='O')>=k) {
            cnt-=(s[l]=='O');
            l++;
        }
        if (cnt==k and dp[l-1]!=INF) dp2[i]=i-l+1-k+dp[l-1];
        else dp2[i]=INF;
        // cout<<dp2[i]<<" ";
    }
    // cout<<"\n";
    l=1;
    cnt=0;
    int ans=INF;
    for (int i=1;i<=n;i++) {
        cnt+=(s[i]=='I');
        while (cnt-(s[l]=='I')>=k) {
            cnt-=(s[l]=='I');
            l++;
        }
        if (cnt==k and dp2[l-1]!=INF) ans=min(ans,i-l+1-k+dp2[l-1]);
        // cout<<ans<<" ";
    }
    cout<<(ans==INF?-1:ans)<<"\n";
    return 0;
}

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