Submission #516189

#	Time	Username	Problem	Language	Result	Execution time	Memory
516189		inksamurai	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	35 ms	15036 KiB

ho_t2

#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
#define rep(i,n) for(int i=0;i<n;i++)
#define crep(i,x,n) for(int i=x;i<n;i++)
#define drep(i,n) for(int i=n-1;i>=0;i--)
#define vec(...) vector<__VA_ARGS__>
#define _34raRxL ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
void print(){cout<<"\n";}
template<class te,class ...ti>
void print(const te&v,const ti&...nv){cout<<v;if(sizeof...(nv)){cout<<" ";print(nv...);}}
//e
typedef long long ll;
typedef long double ld;
using pii=pair<int,int>;
using vi=vector<int>;
 
const int inf=1e9;
 
int main(){
_34raRxL;
	int n,k;
	cin>>n>>k;
	string s;
	cin>>s;
	vi a;
	{
		rep(i,n){
			int x=2;
			if(s[i]=='J') x=0;
			else if(s[i]=='O') x=1;
			a.pb(x);
		}
	}
	vi f_l(n,inf),g(n);
	{
		deque<int> dq;
		bool pok=0;
		rep(i,n){
			int x=a[i];
			if(x!=0){
				if(not pok){
					continue;
				}
			}else{
				pok=1;
			}
			if(i){
				g[i]=g[i-1];
			}
			if(x==0){
				dq.pb(i);
			}else{
				g[i]++;
			}
			if(sz(dq)>k){
				int j=dq.front()+1;
				dq.pop_front();
				while(a[j]!=0){
					g[i]--;
					j=j+1;
				}
			}
			if(sz(dq)==k){
				f_l[i]=g[i];
			}
		}
	} // rabbits from left
	vi f_r(n,inf);
	g=vi(n,0);
	{
		deque<int> dq;
		bool pok=0;
		drep(i,n){
			int x=a[i];
			if(x!=2){
				if(not pok){
					continue;
				}
			}else{
				pok=1;
			}
			if(i!=n-1){
				g[i]=g[i+1];
			}
			if(x==2){
				dq.push_front(i);
			}else{
				g[i]++;
			}
			if(sz(dq)>k){
				int j=dq.back()-1;
				dq.pop_back();
				while(a[j]!=2){
					g[i]--;
					j=j-1;
				}
			}
			if(sz(dq)==k){
				f_r[i]=g[i];
			}
		}
	} // rabbits from right
	vec(vi) psum(n,vi(3));
	rep(i,n){
		if(i){
			psum[i]=psum[i-1];
		}
		psum[i][a[i]]++;
	}
	int ans=inf;
	{
		deque<int> dq;
		int mi=inf,nemi=inf;
		int l=0;
		rep(i,n-1){
			int x=a[i];
			if(x==1){
				dq.pb(i);
			}
			if(sz(dq)>=k){
				if(sz(dq)>k){
					dq.pop_front();
				}
				nemi=inf;
				while(l<dq.front()){
					nemi=min(nemi,f_l[l]-psum[l][0]-psum[l][2]);
					l=l+1;
				}
				mi=min(mi+1,nemi);
				ans=min(ans,mi+f_r[i+1]+psum[i][0]+psum[i][2]);
			}
		}
	}
	print((ans==inf?-1:ans),"\n");
//	
	return 0;
}

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