(cache)Submission #67740188 - 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 #67740188

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()))
dp = [[0] * w for _ in range(h)]
dp[h - 1][w - 1] = max(0, p[h + w - 2] - a[h - 1][w - 1])
for i in range(h - 1, -1, -1):
    for j in range(w - 1, -1, -1):
        if i == h - 1 and j == w - 1:
            continue
        val = p[i + j]
        mi = float("inf")
        if i + 1 < h:
            mi = min(mi, dp[i + 1][j])
        if j + 1 < w:
            mi = min(mi, dp[i][j + 1])
        dp[i][j] = max(0, mi + val - a[i][j])
print(dp[0][0])
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

h, w = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(h)]
p = list(map(int, input().split()))
dp = [[0] * w for _ in range(h)]
dp[h - 1][w - 1] = max(0, p[h + w - 2] - a[h - 1][w - 1])
for i in range(h - 1, -1, -1):
    for j in range(w - 1, -1, -1):
        if i == h - 1 and j == w - 1:
            continue
        val = p[i + j]
        mi = float("inf")
        if i + 1 < h:
            mi = min(mi, dp[i + 1][j])
        if j + 1 < w:
            mi = min(mi, dp[i][j + 1])
        dp[i][j] = max(0, mi + val - a[i][j])
print(dp[0][0])

Submission Info

Submission Time	2025-07-19 21:58:13
Task	E - Hungry Takahashi
User	practicejoi
Language	Python (PyPy 3.10-v7.3.12)
Score	450
Code Size	589 Byte
Status	AC
Exec Time	221 ms
Memory	153448 KiB

Judge Result

Set Name

Sample

All

Score / Max Score

0 / 0

450 / 450

Status

× 3

× 46

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	59 ms	76416 KiB
00_sample_01.txt	AC	59 ms	76276 KiB
00_sample_02.txt	AC	61 ms	76368 KiB
01_random_00.txt	AC	118 ms	118980 KiB
01_random_01.txt	AC	120 ms	117908 KiB
01_random_02.txt	AC	117 ms	118912 KiB
01_random_03.txt	AC	124 ms	124812 KiB
01_random_04.txt	AC	106 ms	94564 KiB
01_random_05.txt	AC	103 ms	94168 KiB
01_random_06.txt	AC	97 ms	92068 KiB
01_random_07.txt	AC	106 ms	91400 KiB
01_random_08.txt	AC	103 ms	85116 KiB
01_random_09.txt	AC	97 ms	85472 KiB
01_random_10.txt	AC	95 ms	85840 KiB
01_random_11.txt	AC	105 ms	86132 KiB
01_random_12.txt	AC	111 ms	86584 KiB
01_random_13.txt	AC	107 ms	86592 KiB
01_random_14.txt	AC	104 ms	86636 KiB
01_random_15.txt	AC	111 ms	86452 KiB
01_random_16.txt	AC	115 ms	86116 KiB
01_random_17.txt	AC	115 ms	86044 KiB
01_random_18.txt	AC	115 ms	88264 KiB
01_random_19.txt	AC	121 ms	88432 KiB
01_random_20.txt	AC	163 ms	117796 KiB
01_random_21.txt	AC	163 ms	116728 KiB
01_random_22.txt	AC	168 ms	118056 KiB
01_random_23.txt	AC	168 ms	116688 KiB
01_random_24.txt	AC	221 ms	153448 KiB
01_random_25.txt	AC	220 ms	144352 KiB
01_random_26.txt	AC	204 ms	130504 KiB
01_random_27.txt	AC	203 ms	137892 KiB
02_random2_00.txt	AC	93 ms	85948 KiB
02_random2_01.txt	AC	93 ms	86408 KiB
02_random2_02.txt	AC	94 ms	86500 KiB
02_random2_03.txt	AC	93 ms	86184 KiB
02_random2_04.txt	AC	91 ms	86392 KiB
02_random2_05.txt	AC	92 ms	86304 KiB
03_handmade_00.txt	AC	57 ms	76472 KiB
03_handmade_01.txt	AC	58 ms	76464 KiB
03_handmade_02.txt	AC	58 ms	76484 KiB
03_handmade_03.txt	AC	85 ms	83796 KiB
03_handmade_04.txt	AC	91 ms	86000 KiB
03_handmade_05.txt	AC	92 ms	86228 KiB
03_handmade_06.txt	AC	109 ms	123524 KiB
03_handmade_07.txt	AC	109 ms	119724 KiB
03_handmade_08.txt	AC	117 ms	120172 KiB