Submission #1238239

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238239		caterpillow	Collecting Mushrooms (NOI18_collectmushrooms)	Pypy 3	100 / 100	192 ms	60380 KiB

mushrooms

rs, cs, d, k = map(int, input().split())
grid = [input() for r in range(rs)]
pfx = [[0] * (cs + 1) for _ in range(rs + 1)]

for r in range(rs):
    for c in range(cs):
        if grid[r][c] == 'S':
            r1 = max(0, r - d)
            c1 = max(0, c - d)
            r2 = min(rs, r + d + 1)
            c2 = min(cs, c + d + 1)
            pfx[r1][c1] += 1
            pfx[r1][c2] -= 1
            pfx[r2][c1] -= 1
            pfx[r2][c2] += 1
for r in range(rs + 1):
    for c in range(cs):
        pfx[r][c + 1] += pfx[r][c]
for r in range(rs):
    for c in range(cs + 1):
        pfx[r + 1][c] += pfx[r][c]

ans = 0
for r in range(rs):
    for c in range(cs):
        if pfx[r][c] >= k and grid[r][c] == 'M':
            ans += 1

print(ans)

Compilation message (stdout)

Compiling 'mushrooms.py'...

=======
  adding: __main__.pyc (deflated 45%)

=======

• Subtask 1: 9 / 9
• Subtask 2: 10 / 10
• Subtask 3: 18 / 18
• Subtask 4: 23 / 23
• Subtask 5: 19 / 19
• Subtask 6: 21 / 21