█████████ ████ ███░░░░░███ ░░███ ███ ░░░ ██████ ███████ ██████ ██████ ░███ ███░░███ ███░░███ ███░░███ ███░░███ ░███ ░███ ░███░███ ░███ ░███████ ░███ ░███ ░░███ ███░███ ░███░███ ░███ ░███░░░ ░███ ░███ ░░█████████ ░░██████ ░░████████░░██████ ░░██████ ░░░░░░░░░ ░░░░░░ ░░░░░░░░ ░░░░░░ ░░░░░░

Envío 5361

Problema 0xcb - Contar maneras de formar una cantidad con monedas

  • Autor: Ikerlb
  • Fecha: 2021-11-24 07:49:15 UTC (Hace más de 2 años)
Caso # Resultado Tiempo Memoria
#1
Incorrecto
0.028 s 4 KBi
#2
Incorrecto
0.026 s 4 KBi
#3
Incorrecto
0.03 s 3 KBi
#4
Incorrecto
0.028 s 3 KBi
#5
Incorrecto
0.097 s 3 KBi
#6
Incorrecto
0.094 s 3 KBi
#7
Incorrecto
0.104 s 4 KBi
#8
Incorrecto
0.093 s 4 KBi
#9
Incorrecto
0.335 s 42 KBi
#10
Incorrecto
0.416 s 45 KBi
#11
Incorrecto
0.441 s 45 KBi
#12
Incorrecto
0.258 s 23 KBi
#13
Correcto
0.445 s 42 KBi
#14
Incorrecto
0.412 s 43 KBi
#15
Incorrecto
0.11 s 4 KBi
Puntos totales: 7 / 100

Código

MOD = 10 ** 9 + 7
N = int(input())
coins = list(map(int, input().split(" ")))
M = int(input())
MOD = 10**9 + 7

dp = [[0]*len(coins) for _ in range(10001)]
for j in range(len(coins)):
    dp[0][j] = 1
for i in range(N + 1):
    for j in range(len(coins)):
        dp[i][j] = dp[i][j - 1]
        if i - coins[j] >= 0:
            dp[i][j] = (dp[i][j] + dp[i - coins[j]][j]) % MOD

for _ in range(M):
    n = int(input())
    print(dp[n][-1])