Submission #1189745

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189745		boclobanchat	JJOOII 2 (JOI20_ho_t2)	C++20	100 / 100	13 ms	8968 KiB

ho_t2

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+5;
int dp[MAXN][4],F[MAXN][4],A[MAXN],cnt[MAXN][4];
vector<int> vi[4];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,k;
    string s;
    cin>>n>>k>>s;
    s=' '+s;
    for(int i=1;i<=n;i++) if(s[i]=='J') A[i]=1;
    else if(s[i]=='O') A[i]=2;
    else A[i]=3;
    for(int i=1;i<=n;i++)
    {
    	vi[A[i]].push_back(i);
    	for(int j=0;j<=3;j++) cnt[i][j]=vi[j].size(),dp[i][j]=1e9;
	}
	dp[0][1]=dp[0][2]=dp[0][3]=1e9;
    for(int i=1;i<=n;i++)
    {
    	for(int j=0;j<=3;j++)
    	{
    		dp[i][j]=dp[i-1][j]+(j>0);
    		if(j&&cnt[i][j]>=k) dp[i][j]=min(dp[i][j],dp[vi[j][cnt[i][j]-k]-1][j-1]+i-vi[j][cnt[i][j]-k]+1-k);
		}
	}
	int ans=1e9;
	for(int i=1;i<=n;i++) ans=min(ans,dp[i][3]);
	if(ans>n) cout<<-1;
	else cout<<ans;
}

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