//
// main.cpp
// HAZ
//
// Created by Nurbek Nurbagi
//
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#define pb push_back
#define ppb pop_back
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
typedef long double ld;
typedef long long ll;
using namespace std;
int gcd (int a, int b) {
while (b) {
a %= b;
swap (a, b);
}
return a;
}
const ll N = 2e5 + 7;
const ll mod = 1e9 + 7;
const ll inf = 1e18;
const ld pi = 3.141592653589793;
const ld eps = 1e-12;
const ll zero = 0;
const int A = 1e9 + 5;
const int dx[4] = {0, -1, 0, 0};
const int dy[4] = {1, 0, -1, 1};
vector <ll> j(N), o(N), i(N);
ll get (int k, int mn, ll l, ll r, char c) {
vector <ll> d;
if (c == 'j') d = j;
if (c == 'o') d = o;
if (c == 'i') d = i;
int x=r;
while (l <= r) {
int mid = (l + r) / 2;
if ( d[mid] >= mn ){
r = mid-1;
x = mid;
}
else l = mid+1;
}
return x;
}
void solve() {
int n, k;
cin >> n >> k;
string s;
cin >> s;
s = 'm' + s;
for (int q = 1; q <= n; q++) {
j[q] = j[q - 1] + (s[q] == 'J');
o[q] = o[q - 1] + (s[q] == 'O');
i[q] = i[q - 1] + (s[q] == 'I');
}
ll mx = 1e18;
for (int q = 1; q <= n; q++) {
if (s[q] != 'J') continue;
int x = j[q] + k - 1;
ll cnt = get(k, x, q, n + 1, 'j');
if (cnt == n + 1) break;
x = o[cnt] + k;
ll cnt2 = get(k, x, cnt + 1, n + 1, 'o');
if (cnt2 == n + 1) break;
x = i[cnt2] + k;
ll cnt3 = get(k, x, cnt2 + 1, n + 1, 'i');
if (cnt3 == n + 1) break;
cnt3 = (cnt3 - q + 1);
mx = min(cnt3, mx);
}
if (mx == 1e18) {
cout << -1;
return;
}
cout << mx - (k * 3);
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
// freopen("herding.in","r",stdin);
// freopen("herding.out","w",stdout);
int t = 1;
// cin >> t;
for (int i = 1; i <= t; i++) solve();
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
6568 KB |
Output is correct |
2 |
Correct |
6 ms |
6572 KB |
Output is correct |
3 |
Correct |
7 ms |
6500 KB |
Output is correct |
4 |
Correct |
6 ms |
6584 KB |
Output is correct |
5 |
Correct |
5 ms |
6584 KB |
Output is correct |
6 |
Correct |
5 ms |
6584 KB |
Output is correct |
7 |
Correct |
4 ms |
6584 KB |
Output is correct |
8 |
Correct |
4 ms |
6568 KB |
Output is correct |
9 |
Correct |
4 ms |
6524 KB |
Output is correct |
10 |
Correct |
4 ms |
6568 KB |
Output is correct |
11 |
Correct |
4 ms |
6572 KB |
Output is correct |
12 |
Correct |
4 ms |
6584 KB |
Output is correct |
13 |
Correct |
5 ms |
6584 KB |
Output is correct |
14 |
Correct |
4 ms |
6584 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
6568 KB |
Output is correct |
2 |
Correct |
6 ms |
6572 KB |
Output is correct |
3 |
Correct |
7 ms |
6500 KB |
Output is correct |
4 |
Correct |
6 ms |
6584 KB |
Output is correct |
5 |
Correct |
5 ms |
6584 KB |
Output is correct |
6 |
Correct |
5 ms |
6584 KB |
Output is correct |
7 |
Correct |
4 ms |
6584 KB |
Output is correct |
8 |
Correct |
4 ms |
6568 KB |
Output is correct |
9 |
Correct |
4 ms |
6524 KB |
Output is correct |
10 |
Correct |
4 ms |
6568 KB |
Output is correct |
11 |
Correct |
4 ms |
6572 KB |
Output is correct |
12 |
Correct |
4 ms |
6584 KB |
Output is correct |
13 |
Correct |
5 ms |
6584 KB |
Output is correct |
14 |
Correct |
4 ms |
6584 KB |
Output is correct |
15 |
Correct |
193 ms |
6596 KB |
Output is correct |
16 |
Correct |
299 ms |
6584 KB |
Output is correct |
17 |
Correct |
269 ms |
6588 KB |
Output is correct |
18 |
Correct |
55 ms |
6568 KB |
Output is correct |
19 |
Correct |
228 ms |
6592 KB |
Output is correct |
20 |
Correct |
224 ms |
6584 KB |
Output is correct |
21 |
Correct |
81 ms |
6584 KB |
Output is correct |
22 |
Correct |
5 ms |
6612 KB |
Output is correct |
23 |
Correct |
5 ms |
6584 KB |
Output is correct |
24 |
Correct |
5 ms |
6584 KB |
Output is correct |
25 |
Correct |
6 ms |
6548 KB |
Output is correct |
26 |
Correct |
6 ms |
6584 KB |
Output is correct |
27 |
Correct |
8 ms |
6612 KB |
Output is correct |
28 |
Correct |
6 ms |
6564 KB |
Output is correct |
29 |
Correct |
4 ms |
6584 KB |
Output is correct |
30 |
Correct |
4 ms |
6584 KB |
Output is correct |
31 |
Correct |
4 ms |
6584 KB |
Output is correct |
32 |
Correct |
5 ms |
6560 KB |
Output is correct |
33 |
Correct |
263 ms |
6596 KB |
Output is correct |
34 |
Correct |
181 ms |
6584 KB |
Output is correct |
35 |
Correct |
5 ms |
6572 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
6568 KB |
Output is correct |
2 |
Correct |
6 ms |
6572 KB |
Output is correct |
3 |
Correct |
7 ms |
6500 KB |
Output is correct |
4 |
Correct |
6 ms |
6584 KB |
Output is correct |
5 |
Correct |
5 ms |
6584 KB |
Output is correct |
6 |
Correct |
5 ms |
6584 KB |
Output is correct |
7 |
Correct |
4 ms |
6584 KB |
Output is correct |
8 |
Correct |
4 ms |
6568 KB |
Output is correct |
9 |
Correct |
4 ms |
6524 KB |
Output is correct |
10 |
Correct |
4 ms |
6568 KB |
Output is correct |
11 |
Correct |
4 ms |
6572 KB |
Output is correct |
12 |
Correct |
4 ms |
6584 KB |
Output is correct |
13 |
Correct |
5 ms |
6584 KB |
Output is correct |
14 |
Correct |
4 ms |
6584 KB |
Output is correct |
15 |
Correct |
193 ms |
6596 KB |
Output is correct |
16 |
Correct |
299 ms |
6584 KB |
Output is correct |
17 |
Correct |
269 ms |
6588 KB |
Output is correct |
18 |
Correct |
55 ms |
6568 KB |
Output is correct |
19 |
Correct |
228 ms |
6592 KB |
Output is correct |
20 |
Correct |
224 ms |
6584 KB |
Output is correct |
21 |
Correct |
81 ms |
6584 KB |
Output is correct |
22 |
Correct |
5 ms |
6612 KB |
Output is correct |
23 |
Correct |
5 ms |
6584 KB |
Output is correct |
24 |
Correct |
5 ms |
6584 KB |
Output is correct |
25 |
Correct |
6 ms |
6548 KB |
Output is correct |
26 |
Correct |
6 ms |
6584 KB |
Output is correct |
27 |
Correct |
8 ms |
6612 KB |
Output is correct |
28 |
Correct |
6 ms |
6564 KB |
Output is correct |
29 |
Correct |
4 ms |
6584 KB |
Output is correct |
30 |
Correct |
4 ms |
6584 KB |
Output is correct |
31 |
Correct |
4 ms |
6584 KB |
Output is correct |
32 |
Correct |
5 ms |
6560 KB |
Output is correct |
33 |
Correct |
263 ms |
6596 KB |
Output is correct |
34 |
Correct |
181 ms |
6584 KB |
Output is correct |
35 |
Correct |
5 ms |
6572 KB |
Output is correct |
36 |
Execution timed out |
2062 ms |
7048 KB |
Time limit exceeded |
37 |
Halted |
0 ms |
0 KB |
- |