Submission #38930523

Source Code Expand

N, X = map(int, input().split())
A = list(map(int, input().split()))

INF = pow(10, 12)

ans = pow(10, 18)+1

for k in range(1, N+1):
    dp = [[[-INF for _ in range(k)] for _ in range(k+1)] for _ in range(N+1)]
    dp[0][0][0] = 0

    for i in range(1, N+1):
        for j in range(k+1):
            for l in range(k):
                if j == 0:
                    dp[i][j][l] = dp[i-1][j][l]
                else:
                    tmp = dp[i-1][j-1][(l-A[i-1])%k]+A[i-1]
                    if tmp <= X:
                        dp[i][j][l] = max(dp[i-1][j][l], tmp)
                    else:
                        dp[i][j][l] = dp[i-1][j][l]


    tmp = dp[N][k][X%k]

    if tmp < 0:
        continue
    else:
        ans = min(ans, (X-tmp)//k)

print(ans)

Submission Info

Submission Time
Task F - Potion
User tamlog06
Language PyPy3 (7.3.0)
Score 600
Code Size 798 Byte
Status AC
Exec Time 1521 ms
Memory 235112 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
AC × 2
AC × 34
Set Name Test Cases
Sample sample_01.txt, sample_02.txt
All hand_01.txt, hand_02.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, random_20.txt, sample_01.txt, sample_02.txt, special_01.txt, special_02.txt, special_03.txt, special_04.txt, special_05.txt, special_06.txt, special_07.txt, special_08.txt, special_09.txt, special_10.txt
Case Name Status Exec Time Memory
hand_01.txt AC 1396 ms 232300 KiB
hand_02.txt AC 1416 ms 235112 KiB
random_01.txt AC 1521 ms 232524 KiB
random_02.txt AC 62 ms 61964 KiB
random_03.txt AC 1488 ms 234960 KiB
random_04.txt AC 206 ms 87672 KiB
random_05.txt AC 1514 ms 232600 KiB
random_06.txt AC 1259 ms 233384 KiB
random_07.txt AC 1506 ms 232612 KiB
random_08.txt AC 98 ms 73580 KiB
random_09.txt AC 1504 ms 234036 KiB
random_10.txt AC 90 ms 73792 KiB
random_11.txt AC 1499 ms 232352 KiB
random_12.txt AC 92 ms 73692 KiB
random_13.txt AC 1493 ms 232592 KiB
random_14.txt AC 218 ms 90508 KiB
random_15.txt AC 1496 ms 232608 KiB
random_16.txt AC 148 ms 77976 KiB
random_17.txt AC 1425 ms 234672 KiB
random_18.txt AC 90 ms 73768 KiB
random_19.txt AC 1511 ms 234788 KiB
random_20.txt AC 95 ms 73632 KiB
sample_01.txt AC 53 ms 61940 KiB
sample_02.txt AC 46 ms 61812 KiB
special_01.txt AC 1419 ms 232520 KiB
special_02.txt AC 1419 ms 232532 KiB
special_03.txt AC 1410 ms 232032 KiB
special_04.txt AC 1413 ms 232396 KiB
special_05.txt AC 1446 ms 232128 KiB
special_06.txt AC 1425 ms 233632 KiB
special_07.txt AC 1416 ms 233744 KiB
special_08.txt AC 1412 ms 234084 KiB
special_09.txt AC 1437 ms 233740 KiB
special_10.txt AC 1416 ms 233684 KiB