Submission #286547

#TimeUsernameProblemLanguageResultExecution timeMemory
286547errorgornJJOOII 2 (JOI20_ho_t2)C++14
100 / 100
12 ms2052 KiB
//雪花飄飄北風嘯嘯
//天地一片蒼茫

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << " is " << x << endl

#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
//change less to less_equal for non distinct pbds, but erase will bug

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

int n,k;
string s;

vector<int> v[3];

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin.exceptions(ios::badbit | ios::failbit);
	
	cin>>n>>k;
	cin>>s;
	
	rep(x,0,n){
		if (s[x]=='J') v[0].push_back(x);
		else if (s[x]=='O') v[1].push_back(x);
		else v[2].push_back(x);
	}
	
	int ans=1e9;
	rep(x,k-1,sz(v[0])){
		int idx=x;
		
		idx=distance(v[1].begin(),lower_bound(all(v[1]),v[0][idx]))+k-1;
		if (sz(v[1])<=idx) break;
		idx=distance(v[2].begin(),lower_bound(all(v[2]),v[1][idx]))+k-1;
		if (sz(v[2])<=idx) break;
		
		ans=min(ans,v[2][idx]-v[0][x-k+1]+1);
	}
	
	if (ans==1e9) cout<<"-1"<<endl;
	else cout<<ans-3*k<<endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...