Submission #226462

#	Time	Username	Problem	Language	Result	Execution time	Memory
226462		thebes	JJOOII 2 (JOI20_ho_t2)	C++14	100 / 100	25 ms	5812 KiB

ho_t2

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

const int MN = 2e5+5;
int N, K, i, j, psa[MN][3], dp[MN][3], ans=1<<30;
string s;

int main(){
    cin >> N >> K >> s;
    s.insert(s.begin(),' ');
    for(i=1;i<=N;i++){
        for(j=0;j<3;j++)
            psa[i][j]=psa[i-1][j];
        if(s[i]=='J') psa[i][0]++;
        else if(s[i]=='O') psa[i][1]++;
        else if(s[i]=='I') psa[i][2]++;
    }
    memset(dp,-1,sizeof(dp));
    for(int k=0;k<3;k++){
        for(i=j=1;i<=N;i++){
            while(j+1<=i&&psa[i][k]-psa[j][k]>=K) j++;
            if(psa[i][k]-psa[j-1][k]<K) continue;
            if(!k) dp[i][k]=i-j+1-K;
            else if(dp[j-1][k-1]!=-1) dp[i][k]=dp[j-1][k-1]+i-j+1-K;
        }
    }
    for(i=1;i<=N;i++){
        if(dp[i][2]!=-1) ans=min(ans,dp[i][2]);
    }
    printf("%d\n",ans==1<<30?-1:ans);
    return 0;
}

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