Submission #636935

#	Time	Username	Problem	Language	Result	Execution time	Memory
636935		beaconmc	JJOOII 2 (JOI20_ho_t2)	Pypy 3	0 / 100	34 ms	18156 KiB

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):
    a = bisect_left(pref1,k+i)
    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-a-2*k)
    print(a,b,c)
print(ans)

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