Submission #636937

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
636937	2022-08-30T15:02:59 Z	beaconmc	JJOOII 2 (JOI20_ho_t2)	PyPy 3	0 / 100	39 ms	18268 KB

ho_t2

from bisect import *
from math import *
n,k = map(int, input().split())
s = input()

pref1 = [int(s[0]=="J")]
pref2 = [int(s[0]=="O")]
pref3 = [int(s[0]=="I")]

for i in range(1,n):
    pref1.append(pref1[-1]+(s[i]=="J"))
    pref2.append(pref2[-1]+(s[i]=="O"))
    pref3.append(pref3[-1]+(s[i]=="I"))

ans = n+1
for i in range(n):
    p = bisect_left(pref1,i+1)
    a = bisect_left(pref1,i+k)
    if a>=n:continue
    b = bisect_left(pref2, pref2[a]+k)
    if b>=n:continue
    c = bisect_left(pref3, pref3[b]+k)
    if c>=n:continue

    ans = min(ans, c-p+1-3*k)

print(ans)

Subtask #1

0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	33 ms	18220 KB	Output is correct
2	Correct	33 ms	18264 KB	Output is correct
3	Correct	33 ms	18256 KB	Output is correct
4	Correct	33 ms	18216 KB	Output is correct
5	Correct	33 ms	18224 KB	Output is correct
6	Correct	39 ms	18204 KB	Output is correct
7	Correct	34 ms	18212 KB	Output is correct
8	Correct	37 ms	18268 KB	Output is correct
9	Incorrect	33 ms	18236 KB	Output isn't correct
10	Halted	0 ms	0 KB	-

Subtask #2

0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	33 ms	18220 KB	Output is correct
2	Correct	33 ms	18264 KB	Output is correct
3	Correct	33 ms	18256 KB	Output is correct
4	Correct	33 ms	18216 KB	Output is correct
5	Correct	33 ms	18224 KB	Output is correct
6	Correct	39 ms	18204 KB	Output is correct
7	Correct	34 ms	18212 KB	Output is correct
8	Correct	37 ms	18268 KB	Output is correct
9	Incorrect	33 ms	18236 KB	Output isn't correct
10	Halted	0 ms	0 KB	-

Subtask #3

0 / 87.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	33 ms	18220 KB	Output is correct
2	Correct	33 ms	18264 KB	Output is correct
3	Correct	33 ms	18256 KB	Output is correct
4	Correct	33 ms	18216 KB	Output is correct
5	Correct	33 ms	18224 KB	Output is correct
6	Correct	39 ms	18204 KB	Output is correct
7	Correct	34 ms	18212 KB	Output is correct
8	Correct	37 ms	18268 KB	Output is correct
9	Incorrect	33 ms	18236 KB	Output isn't correct
10	Halted	0 ms	0 KB	-