Submission #38930523

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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:
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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

Judge Result