Envío 5362

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

Autor: Ikerlb
Fecha: 2021-11-24 07:51:21 UTC (Hace más de 2 años)

Caso #	Resultado	Tiempo	Memoria
#1	Correcto	0.072 s	4 KBi
#2	Correcto	0.122 s	6 KBi
#3	Correcto	0.048 s	4 KBi
#4	Correcto	0.049 s	3 KBi
#5	Correcto	0.112 s	3 KBi
#6	Correcto	0.172 s	4 KBi
#7	Correcto	0.143 s	4 KBi
#8	Correcto	0.162 s	4 KBi
#9	Tiempo límite excedido	1.529 s	42 KBi
#10	Tiempo límite excedido	1.571 s	63 KBi
#11	Tiempo límite excedido	1.566 s	78 KBi
#12	Tiempo límite excedido	1.587 s	57 KBi
#13	Tiempo límite excedido	1.599 s	42 KBi
#14	Tiempo límite excedido	1.578 s	70 KBi
#15	Correcto	0.176 s	5 KBi

Puntos totales: 60 / 100

Código

MOD = 10 ** 9 + 7
_ = 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(10001):
    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])