Submission #72575625


Source Code Expand

# import sys,bisect
from heapq import heappop, heappush
from collections import deque, Counter, defaultdict

inf = 2 ** 63 - 1
mod = 998244353

H,W = list(map(int, input().split()))
S = [list(input()) for _ in range(H)]

class CumulativeSum2D:
    def __init__(self, W, H):
        # data[x][y] で扱う(外側が x, 内側が y)
        self.data = [[0] * (H+1) for _ in range(W+1)]

    def add(self, x, y, z):
        # 0-indexed で (x, y) に値 z を加える
        x += 1
        y += 1
        if x >= len(self.data) or y >= len(self.data[0]):
            return
        self.data[x][y] += z

    def build(self):
        # 2 次元累積和を構築
        for i in range(1, len(self.data)):
            for j in range(1, len(self.data[i])):
                self.data[i][j] += self.data[i][j-1] + self.data[i-1][j] - self.data[i-1][j-1]

    def query(self, sx, sy, gx, gy):
        """
        [sx, gx) × [sy, gy) の長方形の和を返す
        ここで引数は 0-indexed, 右端/下端は「開区間」(C++版と同じ)
        """
        return (
            self.data[gx][gy] - self.data[sx][gy] - self.data[gx][sy] + self.data[sx][sy]
        )


E = CumulativeSum2D(H,W)
F = CumulativeSum2D(H,W)
for i in range(H):
    for j in range(W):
        if S[i][j]=="E": E.add(i,j,1)
        if S[i][j]=="F": F.add(i,j,1)
E.build()
F.build()
ans = 0
nums = [[0]*W for _ in range(H)]
for i in range(H-1):
    for j in range(W):
        nums[i+1][j] += nums[i][j] + E.query(0,0,i,j) * F.query(i,j+1,i+1,W)
# print(nums)
for i in range(H):
    for j in range(W):
        if S[i][j]=="G":
            ans += nums[i][j]
print(ans)
        

Submission Info

Submission Time
Task G - EGFグリッド
User guild2026_288
Language Python (Codon 0.19.3)
Score 100
Code Size 1717 Byte
Status AC
Exec Time 307 ms
Memory 185172 KiB

Compile Error


			

			
				

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
AC × 3
AC × 23
Set Name Test Cases
Sample 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt
All 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 01_random_00.txt, 01_random_01.txt, 01_random_02.txt, 01_random_03.txt, 01_random_04.txt, 01_random_05.txt, 01_random_06.txt, 01_random_07.txt, 01_random_08.txt, 01_random_09.txt, 01_random_10.txt, 01_random_11.txt, 01_random_12.txt, 01_random_13.txt, 01_random_14.txt, 01_random_15.txt, 01_random_16.txt, 01_random_17.txt, 01_random_18.txt, 01_random_19.txt
Case Name Status Exec Time Memory
00_sample_00.txt AC 14 ms 9132 KiB
00_sample_01.txt AC 13 ms 9420 KiB
00_sample_02.txt AC 13 ms 9420 KiB
01_random_00.txt AC 112 ms 74092 KiB
01_random_01.txt AC 46 ms 39756 KiB
01_random_02.txt AC 112 ms 73940 KiB
01_random_03.txt AC 307 ms 185044 KiB
01_random_04.txt AC 138 ms 98436 KiB
01_random_05.txt AC 192 ms 135632 KiB
01_random_06.txt AC 241 ms 144460 KiB
01_random_07.txt AC 300 ms 185044 KiB
01_random_08.txt AC 53 ms 40300 KiB
01_random_09.txt AC 241 ms 161012 KiB
01_random_10.txt AC 18 ms 13416 KiB
01_random_11.txt AC 85 ms 61460 KiB
01_random_12.txt AC 92 ms 64844 KiB
01_random_13.txt AC 295 ms 185172 KiB
01_random_14.txt AC 167 ms 108932 KiB
01_random_15.txt AC 86 ms 61536 KiB
01_random_16.txt AC 256 ms 185164 KiB
01_random_17.txt AC 256 ms 184936 KiB
01_random_18.txt AC 257 ms 185064 KiB
01_random_19.txt AC 258 ms 185040 KiB