(cache)Submission #66763051 - AtCoder Beginner Contest 410

Contest Duration: 2025-06-14(Sat) 21:00 - 2025-06-14(Sat) 22:40 (local time) (100 minutes) Back to Home

Submission #66763051

Source Code Expand

Copy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
for _ in range(int(input())):
    h, w = map(int, input().split())
    grid = [input() for _ in range(h)]
    if h > w:
        grid = [''.join(grid[i][j] for i in range(h)) for j in range(w)]
        h, w = w, h
    a = [[1 if ch == '#' else -1 for ch in row] for row in grid]
    pre = [[0]*w for _ in range(h+1)]
    for i in range(h):
        for j in range(w):
            pre[i+1][j] = pre[i][j] + a[i][j]
    ans = 0
    for u in range(h):
        for d in range(u, h):
            cnt = {0: 1}
            s = 0
            for j in range(w):
                col_sum = pre[d+1][j] - pre[u][j]
                s += col_sum
                ans += cnt.get(s, 0)
                cnt[s] = cnt.get(s, 0) + 1
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

for _ in range(int(input())):
    h, w = map(int, input().split())
    grid = [input() for _ in range(h)]
    if h > w:
        grid = [''.join(grid[i][j] for i in range(h)) for j in range(w)]
        h, w = w, h
    a = [[1 if ch == '#' else -1 for ch in row] for row in grid]
    pre = [[0]*w for _ in range(h+1)]
    for i in range(h):
        for j in range(w):
            pre[i+1][j] = pre[i][j] + a[i][j]
    ans = 0
    for u in range(h):
        for d in range(u, h):
            cnt = {0: 1}
            s = 0
            for j in range(w):
                col_sum = pre[d+1][j] - pre[u][j]
                s += col_sum
                ans += cnt.get(s, 0)
                cnt[s] = cnt.get(s, 0) + 1
    print(ans)

Submission Info

Submission Time	2025-06-14 22:01:26
Task	F - Balanced Rectangles
User	juten
Language	Python (PyPy 3.10-v7.3.12)
Score	0
Code Size	745 Byte
Status	TLE
Exec Time	3318 ms
Memory	151396 KiB

Judge Result

Set Name

Sample

All

Score / Max Score

0 / 0

0 / 525

Status

× 1

AC	× 40
TLE	× 3

Set Name	Test Cases
Sample	sample_01.txt
All	hand_01.txt, hand_02.txt, hand_03.txt, hand_04.txt, sample_01.txt, test_01.txt, test_02.txt, test_03.txt, test_04.txt, test_05.txt, test_06.txt, test_07.txt, test_08.txt, test_09.txt, test_10.txt, test_11.txt, test_12.txt, test_13.txt, test_14.txt, test_15.txt, test_16.txt, test_17.txt, test_18.txt, test_19.txt, test_20.txt, test_21.txt, test_22.txt, test_23.txt, test_24.txt, test_25.txt, test_26.txt, test_27.txt, test_28.txt, test_29.txt, test_30.txt, test_31.txt, test_32.txt, test_33.txt, test_34.txt, test_35.txt, test_36.txt, test_37.txt, test_38.txt

Case Name	Status	Exec Time	Memory
hand_01.txt	AC	187 ms	151396 KiB
hand_02.txt	AC	99 ms	138048 KiB
hand_03.txt	AC	167 ms	102560 KiB
hand_04.txt	AC	78 ms	89076 KiB
sample_01.txt	AC	64 ms	81404 KiB
test_01.txt	AC	59 ms	76512 KiB
test_02.txt	AC	59 ms	76528 KiB
test_03.txt	AC	59 ms	76572 KiB
test_04.txt	AC	61 ms	76388 KiB
test_05.txt	AC	62 ms	76392 KiB
test_06.txt	AC	77 ms	81456 KiB
test_07.txt	AC	78 ms	81972 KiB
test_08.txt	AC	138 ms	84904 KiB
test_09.txt	AC	159 ms	86084 KiB
test_10.txt	AC	194 ms	87204 KiB
test_11.txt	AC	139 ms	84640 KiB
test_12.txt	AC	285 ms	87132 KiB
test_13.txt	AC	193 ms	84684 KiB
test_14.txt	AC	108 ms	118220 KiB
test_15.txt	AC	157 ms	141536 KiB
test_16.txt	AC	2601 ms	98732 KiB
test_17.txt	AC	2143 ms	100820 KiB
test_18.txt	AC	2632 ms	99604 KiB
test_19.txt	AC	2153 ms	100324 KiB
test_20.txt	AC	298 ms	86932 KiB
test_21.txt	AC	2732 ms	89872 KiB
test_22.txt	AC	2369 ms	89896 KiB
test_23.txt	TLE	3046 ms	91200 KiB
test_24.txt	TLE	3318 ms	97188 KiB
test_25.txt	AC	2156 ms	92220 KiB
test_26.txt	AC	1444 ms	90132 KiB
test_27.txt	AC	1051 ms	88240 KiB
test_28.txt	AC	590 ms	88204 KiB
test_29.txt	AC	1064 ms	89640 KiB
test_30.txt	AC	1606 ms	99104 KiB
test_31.txt	TLE	3048 ms	96816 KiB
test_32.txt	AC	1398 ms	91916 KiB
test_33.txt	AC	1670 ms	88088 KiB
test_34.txt	AC	1322 ms	88360 KiB
test_35.txt	AC	1740 ms	88316 KiB
test_36.txt	AC	1136 ms	88632 KiB
test_37.txt	AC	1730 ms	87976 KiB
test_38.txt	AC	602 ms	89008 KiB