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

Envío 6594

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

  • Autor: bryancalisto
  • Fecha: 2022-08-18 01:56:28 UTC (Hace alrededor de 2 meses)
Caso # Resultado Tiempo Memoria
#1
Correcto
0.008 s 2 KBi
#2
Correcto
0.008 s 2 KBi
#3
Correcto
0.007 s 2 KBi
#4
Correcto
0.009 s 2 KBi
#5
Correcto
0.022 s 2 KBi
#6
Correcto
0.036 s 2 KBi
#7
Correcto
0.038 s 2 KBi
#8
Correcto
0.026 s 2 KBi
#9
Correcto
0.121 s 21 KBi
#10
Correcto
0.268 s 21 KBi
#11
Correcto
0.25 s 21 KBi
#12
Correcto
0.154 s 11 KBi
#13
Correcto
0.13 s 21 KBi
#14
Correcto
0.183 s 21 KBi
#15
Correcto
0.032 s 2 KBi
Puntos totales: 100 / 100

Código

#include <bits/stdc++.h>

using namespace std;

int main()
{
  int N;
  int M;
  int nValores = 10001;

  std::cin >> N;
  vector<int> monedas(N);

  for (int i = 0; i < N; i++)
  {
    int mon;
    std::cin >> mon;
    monedas[i] = mon;
  }

  vector<vector<int>> tbl(nValores, vector<int>(N));
  std::cin >> M;
  int valor;

  for (int i = 0; i < N; i++)
  {
    tbl[0][i] = 1;
  }

  for (int i = 0; i < nValores; i++)
  {
    for (int j = 0; j < N; j++)
    {
      if (j > 0)
      {
        tbl[i][j] = tbl[i][j - 1];
      }

      int restante = i - monedas[j];

      if (restante >= 0)
      {
        tbl[i][j] = (tbl[i][j] + tbl[restante][j]) % 1000000007;
      }
    }
  }

  for (int i = 0; i < M; i++)
  {
    std::cin >> valor;
    std::cout << tbl[valor][N - 1] << std::endl;
  }

  return 0;
}