(cache)Submission #66131271 - AtCoder Beginner Contest 407

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

Submission #66131271

Source Code Expand

Copy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
t = int(input())
for _ in range(t):
    n = int(input())
    a = []
    while len(a) < 2 * n:
        a.extend(map(int, input().split()))
    dp = [[-1] * (n + 1) for _ in range(2 * n + 1)]
    dp[0][0] = 0
    for i in range(2 * n):
        for j in range(n + 1):
            if dp[i][j] == -1:
                continue
            if j + 1 <= n:
                dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + a[i])
            if j - 1 >= 0:
                dp[i + 1][j - 1] = max(dp[i + 1][j - 1], dp[i][j])
    print(dp[2 * n][0])
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

t = int(input())
for _ in range(t):
    n = int(input())
    a = []
    while len(a) < 2 * n:
        a.extend(map(int, input().split()))
    dp = [[-1] * (n + 1) for _ in range(2 * n + 1)]
    dp[0][0] = 0

    for i in range(2 * n):
        for j in range(n + 1):
            if dp[i][j] == -1:
                continue
            if j + 1 <= n:
                dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + a[i])
            if j - 1 >= 0:
                dp[i + 1][j - 1] = max(dp[i + 1][j - 1], dp[i][j])
    print(dp[2 * n][0])

Submission Info

Submission Time	2025-05-24 22:31:03
Task	E - Most Valuable Parentheses
User	practicejoi
Language	Python (PyPy 3.10-v7.3.12)
Score	0
Code Size	559 Byte
Status	RE
Exec Time	2426 ms
Memory	3620000 KiB

Judge Result

Set Name

Sample

All

Score / Max Score

0 / 0

0 / 450

Status

× 1

AC	× 6
TLE	× 7
RE	× 5

Set Name	Test Cases
Sample	00-sample-01.txt
All	00-sample-01.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt

Case Name	Status	Exec Time	Memory
00-sample-01.txt	AC	57 ms	76528 KiB
01-01.txt	AC	83 ms	82248 KiB
01-02.txt	AC	101 ms	83680 KiB
01-03.txt	AC	111 ms	84512 KiB
01-04.txt	AC	96 ms	84280 KiB
01-05.txt	TLE	2223 ms	316836 KiB
01-06.txt	RE	2039 ms	3618684 KiB
01-07.txt	TLE	2426 ms	3605420 KiB
01-08.txt	AC	1530 ms	215732 KiB
01-09.txt	TLE	2224 ms	334288 KiB
01-10.txt	TLE	2336 ms	3619784 KiB
01-11.txt	RE	1919 ms	3619160 KiB
01-12.txt	TLE	2418 ms	3603720 KiB
01-13.txt	RE	2138 ms	3619792 KiB
01-14.txt	TLE	2420 ms	3617840 KiB
01-15.txt	RE	2122 ms	3620000 KiB
01-16.txt	TLE	2400 ms	3607036 KiB
01-17.txt	RE	1957 ms	3619868 KiB