提出 #17308590


ソースコード 拡げる

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))

提出情報

提出日時
問題 E - Lamps
ユーザ maspy
言語 Python (3.8.2)
得点 500
コード長 1127 Byte
結果 AC
実行時間 722 ms
メモリ 236140 KB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 500 / 500
結果
AC × 2
AC × 19
セット名 テストケース
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
ケース名 結果 実行時間 メモリ
01.txt AC 475 ms 106996 KB
02.txt AC 450 ms 107788 KB
11.txt AC 702 ms 236140 KB
12.txt AC 711 ms 235044 KB
13.txt AC 718 ms 235656 KB
14.txt AC 449 ms 108204 KB
15.txt AC 449 ms 109920 KB
16.txt AC 719 ms 235764 KB
17.txt AC 524 ms 152792 KB
18.txt AC 716 ms 235900 KB
19.txt AC 704 ms 235132 KB
20.txt AC 722 ms 235056 KB
B02.txt AC 447 ms 107244 KB
B11.txt AC 452 ms 107016 KB
B12.txt AC 448 ms 107916 KB
B13.txt AC 446 ms 107236 KB
B14.txt AC 453 ms 107236 KB
B15.txt AC 451 ms 107276 KB
B16.txt AC 451 ms 107216 KB