Submission #216817

#	Time	Username	Problem	Language	Result	Execution time	Memory
216817		oolimry	JJOOII 2 (JOI20_ho_t2)	C++14	100 / 100	11 ms	4740 KiB

ho_t2

#include <bits/stdc++.h>

using namespace std;
typedef pair<long long, long long> ii;
long long inf = 1e9;
long long pre[200005];
long long suf[200005];
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	long long ans = inf;
	int n, k; cin >> n >> k;
	string s; cin >> s;
	vector<int> O;
	
	deque<long long> dq;
	for(int i = 0;i < k;i++) dq.push_back(inf);
	
	for(int i = 0;i < n;i++){
		if(s[i] == 'J'){
			dq.push_back(i);
			dq.pop_front();
		}
		else if(s[i] == 'O'){
			pre[i] = dq.front();
			O.push_back(i);
		}
	}
	
	dq.clear();
	for(int i = 0;i < k;i++) dq.push_back(inf);
	for(int i = n-1;i >= 0;i--){
		if(s[i] == 'I'){
			dq.push_back(i);
			dq.pop_front();
		}
		else if(s[i] == 'O'){
			suf[i] = dq.front();
		}
	}
	
	for(int i = 0;i <= O.size() - k;i++){
		long long L = pre[O[i]];
		long long R = suf[O[i+k-1]];
		if(L == inf || R == inf) continue;
		ans = min(ans, R - L + 1);
	}
	
	if(ans >= inf/2) ans = -1;
	else{
		ans -= 3 * k;
	}
	
	cout << ans;
}

/*
10 2
OJIJOIOIIJ
*/

Compilation message (stderr)

ho_t2.cpp: In function 'int main()':
ho_t2.cpp:43:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0;i <= O.size() - k;i++){
                ~~^~~~~~~~~~~~~~~

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