(cache)Submission #67739065 - Japan Registry Services (JPRS) Programming Contest 2025#2 (AtCoder Beginner Contest 415)

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

Submission #67739065

Source Code Expand

Copy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
h, w = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(h)]
p = list(map(int, input().split()))
X = 10**10
dp = [[X] * (w + 1) for _ in range(h + 1)]
dp[h][w] = max(0, p[h + w - 2] - a[h - 1][w - 1])
for i in reversed(range(1, h + 1)):
    for j in reversed(range(1, w + 1)):
        if i == h and j == w:
            continue
        k = i + j - 2
        up = dp[i][j + 1] + p[k] - a[i - 1][j - 1] if j < w else X
        down = dp[i + 1][j] + p[k] - a[i - 1][j - 1] if i < h else X
        dp[i][j] = min(up, down)
        if dp[i][j] < 0:
            dp[i][j] = 0
print(dp[1][1])
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

h, w = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(h)]
p = list(map(int, input().split()))
X = 10**10
dp = [[X] * (w + 1) for _ in range(h + 1)]
dp[h][w] = max(0, p[h + w - 2] - a[h - 1][w - 1])
for i in reversed(range(1, h + 1)):
    for j in reversed(range(1, w + 1)):
        if i == h and j == w:
            continue
        k = i + j - 2
        up = dp[i][j + 1] + p[k] - a[i - 1][j - 1] if j < w else X
        down = dp[i + 1][j] + p[k] - a[i - 1][j - 1] if i < h else X
        dp[i][j] = min(up, down)
        if dp[i][j] < 0:
            dp[i][j] = 0
print(dp[1][1])

Submission Info

Submission Time	2025-07-19 21:55:33
Task	E - Hungry Takahashi
User	practicejoi
Language	Python (PyPy 3.10-v7.3.12)
Score	0
Code Size	628 Byte
Status	WA
Exec Time	199 ms
Memory	154252 KiB

Judge Result

Set Name

Sample

All

Score / Max Score

0 / 0

0 / 450

Status

× 3

AC	× 28
WA	× 18

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, 01_random_20.txt, 01_random_21.txt, 01_random_22.txt, 01_random_23.txt, 01_random_24.txt, 01_random_25.txt, 01_random_26.txt, 01_random_27.txt, 02_random2_00.txt, 02_random2_01.txt, 02_random2_02.txt, 02_random2_03.txt, 02_random2_04.txt, 02_random2_05.txt, 03_handmade_00.txt, 03_handmade_01.txt, 03_handmade_02.txt, 03_handmade_03.txt, 03_handmade_04.txt, 03_handmade_05.txt, 03_handmade_06.txt, 03_handmade_07.txt, 03_handmade_08.txt

Case Name	Status	Exec Time	Memory
00_sample_00.txt	AC	56 ms	76476 KiB
00_sample_01.txt	AC	56 ms	76596 KiB
00_sample_02.txt	AC	56 ms	76556 KiB
01_random_00.txt	WA	115 ms	119988 KiB
01_random_01.txt	AC	110 ms	117804 KiB
01_random_02.txt	WA	110 ms	119128 KiB
01_random_03.txt	WA	113 ms	124596 KiB
01_random_04.txt	AC	93 ms	94624 KiB
01_random_05.txt	AC	91 ms	94192 KiB
01_random_06.txt	WA	87 ms	91688 KiB
01_random_07.txt	AC	95 ms	91336 KiB
01_random_08.txt	AC	87 ms	84832 KiB
01_random_09.txt	AC	85 ms	84732 KiB
01_random_10.txt	WA	85 ms	85888 KiB
01_random_11.txt	AC	90 ms	85964 KiB
01_random_12.txt	AC	97 ms	86460 KiB
01_random_13.txt	AC	93 ms	86360 KiB
01_random_14.txt	WA	93 ms	83764 KiB
01_random_15.txt	AC	97 ms	86284 KiB
01_random_16.txt	AC	104 ms	86308 KiB
01_random_17.txt	AC	105 ms	86048 KiB
01_random_18.txt	WA	109 ms	88368 KiB
01_random_19.txt	AC	108 ms	88400 KiB
01_random_20.txt	WA	150 ms	118536 KiB
01_random_21.txt	AC	150 ms	117344 KiB
01_random_22.txt	WA	150 ms	118404 KiB
01_random_23.txt	WA	156 ms	117688 KiB
01_random_24.txt	WA	199 ms	154252 KiB
01_random_25.txt	AC	180 ms	128360 KiB
01_random_26.txt	WA	183 ms	130404 KiB
01_random_27.txt	WA	199 ms	137684 KiB
02_random2_00.txt	WA	83 ms	83808 KiB
02_random2_01.txt	WA	85 ms	83692 KiB
02_random2_02.txt	WA	88 ms	86304 KiB
02_random2_03.txt	AC	88 ms	86124 KiB
02_random2_04.txt	AC	86 ms	86060 KiB
02_random2_05.txt	AC	86 ms	86164 KiB
03_handmade_00.txt	AC	55 ms	76416 KiB
03_handmade_01.txt	AC	55 ms	76600 KiB
03_handmade_02.txt	AC	58 ms	76412 KiB
03_handmade_03.txt	WA	84 ms	84080 KiB
03_handmade_04.txt	AC	85 ms	86216 KiB
03_handmade_05.txt	AC	85 ms	86144 KiB
03_handmade_06.txt	WA	102 ms	123896 KiB
03_handmade_07.txt	AC	101 ms	119652 KiB
03_handmade_08.txt	AC	108 ms	121868 KiB