#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 lll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
#define MAX 9223372036854775807LL
#define MIN -9223372036854775807LL
#define INF 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cout << fixed; cout.precision(10);
#define sp << " "
#define en << "\n"
#define compress(v) sort(v.begin(), v.end()), v.erase(unique(v.begin(), v.end()), v.end())
ll n, K;
char a[200010];
ll l, r;
ll nu[200010][5];
ll idx[200010][5];
int main(void)
{
fastio
cin >> n >> K;
for(ll i = 1 ; i <= n ; i++)
{
cin >> a[i];
for(ll j = 0 ; j <= 2 ; j++)
nu[i][j] = nu[i - 1][j];
if(a[i] == 'J')
nu[i][0]++;
else if(a[i] == 'O')
nu[i][1]++;
else
nu[i][2]++;
}
for(ll i = 1 ; i <= n ; i++)
{
for(ll j = 0 ; j <= 2 ; j++)
{
ll l = i, r = n;
while(l <= r)
{
ll mid = (l + r) / 2;
if(nu[mid][j] - nu[i - 1][j] >= K)
r = mid - 1;
else
l = mid + 1;
}
idx[i][j] = l;
}
}
l = 0, r = n - K * 3;
while(l <= r)
{
ll mid = (l + r) / 2;
ll ff = 0;
for(ll i = 0 ; i <= mid ; i++)
{
ll L = 1 + i;
ll R = n - (mid - i);
ll now = L, gg = 0;
for(ll j = 0 ; j <= 2 ; j++)
{
if(now > R)
gg = 1;
now = idx[now][j];
if(now > R)
gg = 1;
now++;
}
if(!gg)
ff = 1;
}
if(ff)
l = mid + 1;
else
r = mid - 1;
}
if(r == -1)
cout << -1;
else
cout << n - K * 3 - r;
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
0 ms |
340 KB |
Output is correct |
11 |
Correct |
0 ms |
340 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
0 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
0 ms |
340 KB |
Output is correct |
11 |
Correct |
0 ms |
340 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
0 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
468 KB |
Output is correct |
16 |
Correct |
1 ms |
468 KB |
Output is correct |
17 |
Correct |
1 ms |
468 KB |
Output is correct |
18 |
Correct |
1 ms |
424 KB |
Output is correct |
19 |
Correct |
1 ms |
468 KB |
Output is correct |
20 |
Correct |
1 ms |
452 KB |
Output is correct |
21 |
Correct |
1 ms |
468 KB |
Output is correct |
22 |
Correct |
1 ms |
468 KB |
Output is correct |
23 |
Correct |
1 ms |
468 KB |
Output is correct |
24 |
Correct |
1 ms |
468 KB |
Output is correct |
25 |
Correct |
1 ms |
584 KB |
Output is correct |
26 |
Correct |
1 ms |
468 KB |
Output is correct |
27 |
Correct |
1 ms |
452 KB |
Output is correct |
28 |
Correct |
1 ms |
468 KB |
Output is correct |
29 |
Correct |
1 ms |
468 KB |
Output is correct |
30 |
Correct |
1 ms |
468 KB |
Output is correct |
31 |
Correct |
1 ms |
340 KB |
Output is correct |
32 |
Correct |
1 ms |
468 KB |
Output is correct |
33 |
Correct |
1 ms |
468 KB |
Output is correct |
34 |
Correct |
1 ms |
468 KB |
Output is correct |
35 |
Correct |
1 ms |
468 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
0 ms |
340 KB |
Output is correct |
11 |
Correct |
0 ms |
340 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
0 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
468 KB |
Output is correct |
16 |
Correct |
1 ms |
468 KB |
Output is correct |
17 |
Correct |
1 ms |
468 KB |
Output is correct |
18 |
Correct |
1 ms |
424 KB |
Output is correct |
19 |
Correct |
1 ms |
468 KB |
Output is correct |
20 |
Correct |
1 ms |
452 KB |
Output is correct |
21 |
Correct |
1 ms |
468 KB |
Output is correct |
22 |
Correct |
1 ms |
468 KB |
Output is correct |
23 |
Correct |
1 ms |
468 KB |
Output is correct |
24 |
Correct |
1 ms |
468 KB |
Output is correct |
25 |
Correct |
1 ms |
584 KB |
Output is correct |
26 |
Correct |
1 ms |
468 KB |
Output is correct |
27 |
Correct |
1 ms |
452 KB |
Output is correct |
28 |
Correct |
1 ms |
468 KB |
Output is correct |
29 |
Correct |
1 ms |
468 KB |
Output is correct |
30 |
Correct |
1 ms |
468 KB |
Output is correct |
31 |
Correct |
1 ms |
340 KB |
Output is correct |
32 |
Correct |
1 ms |
468 KB |
Output is correct |
33 |
Correct |
1 ms |
468 KB |
Output is correct |
34 |
Correct |
1 ms |
468 KB |
Output is correct |
35 |
Correct |
1 ms |
468 KB |
Output is correct |
36 |
Correct |
35 ms |
15180 KB |
Output is correct |
37 |
Correct |
39 ms |
16348 KB |
Output is correct |
38 |
Correct |
38 ms |
16240 KB |
Output is correct |
39 |
Correct |
51 ms |
16132 KB |
Output is correct |
40 |
Correct |
39 ms |
16300 KB |
Output is correct |
41 |
Correct |
48 ms |
16348 KB |
Output is correct |
42 |
Correct |
56 ms |
16344 KB |
Output is correct |
43 |
Correct |
23 ms |
10260 KB |
Output is correct |
44 |
Correct |
27 ms |
12756 KB |
Output is correct |
45 |
Correct |
34 ms |
16332 KB |
Output is correct |
46 |
Correct |
35 ms |
16260 KB |
Output is correct |
47 |
Correct |
34 ms |
16280 KB |
Output is correct |
48 |
Correct |
34 ms |
16260 KB |
Output is correct |
49 |
Correct |
24 ms |
10964 KB |
Output is correct |
50 |
Correct |
34 ms |
16340 KB |
Output is correct |
51 |
Correct |
34 ms |
16296 KB |
Output is correct |
52 |
Correct |
22 ms |
15696 KB |
Output is correct |
53 |
Correct |
24 ms |
16284 KB |
Output is correct |
54 |
Correct |
36 ms |
16344 KB |
Output is correct |
55 |
Correct |
31 ms |
16440 KB |
Output is correct |
56 |
Correct |
20 ms |
16340 KB |
Output is correct |