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

Envío 5356

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

  • Autor: DanielP
  • Fecha: 2021-11-24 05:32:51 UTC (Hace más de 2 años)
Caso # Resultado Tiempo Memoria
#1
Correcto
0.066 s 40 KBi
#2
Correcto
0.048 s 55 KBi
#3
Correcto
0.039 s 40 KBi
#4
Correcto
0.069 s 39 KBi
#5
Tiempo límite excedido
1.054 s 39 KBi
#6
Tiempo límite excedido
1.074 s 39 KBi
#7
Tiempo límite excedido
1.04 s 41 KBi
#8
Tiempo límite excedido
1.101 s 41 KBi
#9
Tiempo límite excedido
1.073 s 43 KBi
#10
Tiempo límite excedido
1.036 s 39 KBi
#11
Tiempo límite excedido
1.089 s 41 KBi
#12
Tiempo límite excedido
1.037 s 40 KBi
#13
Tiempo límite excedido
1.065 s 42 KBi
#14
Tiempo límite excedido
1.071 s 39 KBi
#15
Tiempo límite excedido
1.043 s 41 KBi
Puntos totales: 27 / 100

Código

/// Write by Daniel Perez .PERAPRO
#include<bits/stdc++.h>

using namespace std;
#define fast_io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(), s.end()
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
using vi=vector<int>;
using vl=vector<ll>;
using pii=pair<int,int>;
char el = '\n';
char esp = ' ';

template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

ostream& operator<<(ostream& os, const vector<int> &v){
    for(auto const &i: v){
        os<<i<<" ";
    }
    os<<'\n';
    return os;
}
string yes="YES";
string no="NO";

const int N = 505;
const int maxn = 10005;

ll v[N];

int n;

ll dp[maxn][N];

const ll mod = 1e9+7;

ll go(int val, int idx){
    if(val == 0) return 1;
    if(idx == n || val < 0) return 0;
    
    ll &ans = dp[val][idx];
    
    if(ans == -1){
        ans = 0;
        ans = (ans + go(val - v[idx], idx)) % mod;
        ans = (ans + go(val, idx + 1)) % mod;
    }
    return ans;
}

int main(){
	fast_io;
	/*
 	freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    */
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>v[i];
    }
    int querys;
    cin>>querys;
    while(querys--){
        int s;
        cin>>s;
        memset(dp, -1, sizeof dp);
        cout<<go(s, 0)<<el;
    }
}

/*

*/