제출 #1288900

#제출 시각아이디문제언어결과실행 시간메모리
1288900tunademayoJJOOII 2 (JOI20_ho_t2)C++20
100 / 100
33 ms21100 KiB
#include<bits/stdc++.h>
using namespace std;

#define ll long long 

const bool Multitest = 0;

const int N = 2e5 + 10;

int n, k;
int cnt[N][26]; string s;

int get(int p, int x)
{
	if(p == -1) return p;
	
	int l = p, r = n, pos = -1;
	
	while(l <= r)
	{
		int mid = (l + r) >> 1;
		
//		cout << l << ' ' << r << ' ' << mid << '\n';
		
		if(cnt[mid][x] - cnt[p - 1][x] >= k) r = mid - 1, pos = mid;
		else l = mid + 1;
	}
	
	return pos;
}

void work()
{
	cin >> n >> k >> s;	
	
	s = '0' + s;
	
	for(int i = 1 ; i <= n ; i++)
	{
		for(int j = 0 ; j < 26 ; j++) cnt[i][j] += cnt[i - 1][j];
		cnt[i][s[i] - 'A']++;
	}
	
	vector<int> c;
	
	c.push_back('J' - 'A');
	c.push_back('O' - 'A');
	c.push_back('I' - 'A');
	
	int ans = 1e9;
	
//	cout << get(2, 'J' - 'A') << '\n';
//	return;
	
	for(int i = 1 ; i <= n ; i++)
	{
		if(s[i] == 'J')
		{
			int l = i, r = i;
			for(int x : c)
			{
				r = get(r, x);
				
//				cout << x << ' ' << r << '\n';
			}
			if(r != -1) ans = min(ans, r - l + 1);
		}
	}
	
	cout << (ans != 1e9 ? ans - 3 * k : -1);
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);	cout.tie(0);
	
	int q = 1;
	
	if(Multitest)	cin >> q;
	
	while(q--) work();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...