제출 #1326569

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1326569		Mauricio_Cruz	JJOOII 2 (JOI20_ho_t2)	C++20	100 / 100	27 ms	6972 KiB

ho_t2

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

#define all(x) x.begin(), x.end()

#define srtl(x)sort(all(x))
#define srtg(x)sort((x).begin(),(x).end(),greater<>())
#define rev(x) reverse(all(x))
#define lb(x,y) lower_bound(x.begin(),x.end(),y)-x.begin()
#define ub(x,y) upper_bound(x.begin(),x.end(),y)-x.begin()

#define ios ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

#define f first
#define s second
#define pb push_back
#define ins insert
#define next next_permutation
#define _b __builtin_popcount

#define ve vector
#define pii pair<int,int>
#define piii pair<int,pii>
#define vi vector<int>
#define vii vector<pii>
#define viii vector<piii>
#define vvi vector<vi>
#define vs vector<string>
#define vb vector<bool>

#define pV(x)for(auto i:x)cout<<i<<" ";

#define geta(a){for(auto &i:a)cin>>i;}

#define fr(n)for(int i=0;i<n;i++)
#define Fr(n)for(int i=n-1;i>=0;i--)

#define suma(a)accumulate(a.begin(),a.end(),0LL)

#define br(x){cout<<x<<"\n";return;}
#define yesn cout<<"YES\n";

#define yes()br("YES");
#define no(){br("NO")}

#define alice() br("Alice");
#define bob() br("Bob");

#define cn continue;

#define cint const int
#define int long long


int mod=1000000007;
cint mod1=100000007;
cint mod2=998244353;

int ax[8]={0,1,0,-1,-1,1,1,-1};
int ay[8]={1,0,-1,0,1,-1,1,-1};

//bool on(int x,int y){return (x>=0&&x<n&&y>=0&&y<m);}
//int euc(int a,int b,int c,int d){return abs(a-c)+abs(b-d);}

int bp(int x,int y){
	if(y==0)return 1;
	int r=bp(x,y/2);
	return (y&1)?r*r%mod*x%mod:r*r%mod;
}
int bpm(int x,int y){
	if(y==0)return 1;
	int r=bp(x,y/2);
	return (y&1)?r*r*x:r*r;
}
cint N=200006;
int F[N+1],I[N+1];

int cmb(int n,int k){
	return (((F[n]*I[k])%mod)*I[n-k])%mod;
}

int cinn(){
	int n;
	cin>>n;
	return n;
}
#define w cinn()




void solve(){
	int n,k;
	cin>>n>>k;
	string x;
	cin>>x;
	vi pj(n,0),po(n,0),pi(n,0);
	for(int i=0;i<n;i++){
		if(x[i]=='J')pj[i]++;
		if(x[i]=='O')po[i]++;
		if(x[i]=='I')pi[i]++;
		if(i){
			pj[i]+=pj[i-1];
			po[i]+=po[i-1];
			pi[i]+=pi[i-1];
		}
	}
	vi prj(n+1,1e18);
	for(int i=n-1;i>=0;i--){
		prj[i]=prj[i+1];
		if(x[i]=='J')prj[i]=i;
	}
	int res=1e18;
	for(int i=0;i<n;i++){
		int mi=i-1,ma=n,me;
		int p1=1e18,p2=1e18,p3=1e18;
		while(ma-mi!=1){
			me=(ma+mi)/2;
			if(pj[me]-(i?(pj[i-1]):0)>=k){
				p1=min(p1,me);
				ma=me;
			}
			else mi=me;
		}
		if(p1==1e18)continue;
		mi=p1,ma=n;
		while(ma-mi!=1){
			me=(ma+mi)/2;
			if(po[me]-po[p1]>=k){
				p2=min(p2,me);
				ma=me;
			}
			else mi=me;
		}	
		mi=p2,ma=n;
		if(p2==1e18)continue;
		
		while(ma-mi!=1){
			me=(ma+mi)/2;
			if(pi[me]-pi[p2]>=k){
				p3=min(p3,me);
				ma=me;
			}
			else mi=me;
		}
		if(p3==1e18)continue;
		res=min(res,(p3-(prj[i])+1 - (3*k) ));
	}
	if(res==1e18)res=-1;
	cout<<res;
}

int32_t main(){
	
	ios;

	int t=1;
	//cin>>t;
	
	/*
	F[0]=1;
	for(int i=1;i<=N;i++){
		F[i]=(i*F[i-1])%mod;
	}
	
	I[N]=(bp(F[N],mod-2))%mod;
	for(int i=N-1;i>=0;i--){
		I[i]=(I[i+1]*(i+1))%mod;
	}
	//*/
	
	
	
	while(t--){
		solve();
	}
	
	return 0;
}

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