Submission #11519264


Source Code Expand

Copy
#!/usr/bin/ python3.8
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, K, C = map(int, readline().split())
S = read().rstrip().decode()


def compute(S):
    dp = [0] * N
    for i, x in enumerate(S):
        if i <= C:
            dp[i] = 1
        else:
            if x == 'x':
                dp[i] = dp[i - 1]
            else:
                dp[i] = dp[i - C - 1] + 1
        if dp[i - 1] > dp[i]:
            dp[i] = dp[i - 1]
    return dp


dp1 = compute(S)
dp2 = compute(S[::-1])[::-1]


def get_answers():
    for i in range(N):
        before = dp1[i - 1] if i else 0
        after = dp2[i + 1] if i < N - 1 else 0
        if before + after < K:
            yield i + 1


for x in get_answers():
    print(x)

Submission Info

Submission Time
Task E - Yutori
User maspy
Language Python (3.4.3)
Score 500
Code Size 832 Byte
Status AC
Exec Time 428 ms
Memory 20772 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 500 / 500
Status
AC × 4
AC × 21
Set Name Test Cases
Sample sample_01, sample_02, sample_03, sample_04
All hand_01, hand_02, max_01, max_02, max_03, max_04, max_05, random_01, random_02, random_03, random_04, random_05, random_06, random_07, random_08, random_09, random_10, sample_01, sample_02, sample_03, sample_04
Case Name Status Exec Time Memory
hand_01 AC 18 ms 3064 KB
hand_02 AC 18 ms 3064 KB
max_01 AC 222 ms 16548 KB
max_02 AC 221 ms 16548 KB
max_03 AC 252 ms 12204 KB
max_04 AC 428 ms 20772 KB
max_05 AC 251 ms 20772 KB
random_01 AC 63 ms 4596 KB
random_02 AC 105 ms 5796 KB
random_03 AC 212 ms 11600 KB
random_04 AC 214 ms 11580 KB
random_05 AC 214 ms 11668 KB
random_06 AC 206 ms 11692 KB
random_07 AC 206 ms 11604 KB
random_08 AC 206 ms 11740 KB
random_09 AC 208 ms 11644 KB
random_10 AC 208 ms 11636 KB
sample_01 AC 18 ms 3064 KB
sample_02 AC 18 ms 3064 KB
sample_03 AC 18 ms 3064 KB
sample_04 AC 18 ms 3064 KB