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
Task E - Lamps
User maspy
Language Python (3.8.2)
Score 500
Code Size 1127 Byte
Status
Exec Time 722 ms
Memory 236140 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 500 / 500
Status
× 2
× 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