Contest Duration: ~ (local time) (100 minutes) Back to Home

Submission #17308590

Source Code Expand

Copy
```import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

MOD = 1_000_000_007

@njit((i8[:, :], ), cache=True)
def main(wall):
cnt = np.zeros_like(wall)
for _ in range(4):
cnt, wall = cnt[::-1].T, wall[::-1].T
A = np.zeros_like(cnt)
# 上にあるものを数える。自身は含まない
H, W = A.shape
for h in range(1, H):
x = A[h - 1] + 1
x *= (1 - wall[h - 1])
A[h] = x
cnt += A
cnt = (1 + cnt) * (1 - wall)
H, W = cnt.shape
pow2 = np.ones(H * W + 10, np.int64)
for i in range(H * W + 9):
pow2[i + 1] = pow2[i] * 2 % MOD
ans = 0
K = (1 - wall).sum()
for n in cnt.ravel():
if n == 0:
continue
ans += pow2[K] - pow2[K - n]
return ans % MOD

H, W = map(int, readline().split())
S = np.frombuffer(read(), 'S1').reshape(H, -1)[:, :W]

wall = ((S == b'#') * 1).astype(np.int64)
print(main(wall))```

#### Submission Info

Submission Time 2020-10-10 21:51:53+0900 E - Lamps maspy Python (3.8.2) 500 1127 Byte AC 722 ms 236140 KB

#### Judge Result

Set Name Sample All
Score / Max Score 0 / 0 500 / 500
Status
 AC × 2
 AC × 19
Set Name Test Cases
Sample 01.txt, 02.txt
All 01.txt, 02.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, B02.txt, B11.txt, B12.txt, B13.txt, B14.txt, B15.txt, B16.txt
Case Name Status Exec Time Memory
01.txt 475 ms 106996 KB
02.txt 450 ms 107788 KB
11.txt 702 ms 236140 KB
12.txt 711 ms 235044 KB
13.txt 718 ms 235656 KB
14.txt 449 ms 108204 KB
15.txt 449 ms 109920 KB
16.txt 719 ms 235764 KB
17.txt 524 ms 152792 KB
18.txt 716 ms 235900 KB
19.txt 704 ms 235132 KB
20.txt 722 ms 235056 KB
B02.txt 447 ms 107244 KB
B11.txt 452 ms 107016 KB
B12.txt 448 ms 107916 KB
B13.txt 446 ms 107236 KB
B14.txt 453 ms 107236 KB
B15.txt 451 ms 107276 KB
B16.txt 451 ms 107216 KB