Submission #423375

#	Time	Username	Problem	Language	Result	Execution time	Memory
423375		milleniumEeee	JJOOII 2 (JOI20_ho_t2)	C++17	13 / 100	2071 ms	600 KiB

ho_t2

#include <bits/stdc++.h>
#define fr first
#define sc second
#define pii pair<int, int>
#define pb push_back
#define szof(s) (int)s.size()
#define all(s) s.begin(), s.end()
#define fastInp ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;

const int INF = 1e9;
vector <char> vec = {'J', 'O', 'I', '#'};

int cnt[1000];
int n, k;
string s;

void gg() {
	cout << -1 << endl;
	exit(0);
}

bool can(int l, int r, int k) {
	int cur = 0, count = 0;
	for (int i = l; i <= r; i++) {
		if (s[i] == vec[cur]) {
			count++;
		}
		if (count == k) {
			count = 0;
			cur++;
		}
	}
	return (cur == 3);
}

signed main() {
	fastInp;
	cin >> n >> k;
	cin >> s;
	int ans = INF;
	for (int l = 0; l < n; l++) {
		if (can(l, n - 1, k)) {
			int bl = l, br = n - 1;
			while (br - bl > 1) {
				int bmid = (bl + br) >> 1;
				if (can(l, bmid, k)) {
					br = bmid;
				} else {
					bl = bmid;
				}
			}
			ans = min(ans, (br - l + 1) - k * 3);
		}
	}
	if (ans == INF) {
		gg();
	}
	cout << ans << endl;
}
/*
10 2
OJIJOIOIIJ
*/

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