Caso # | Resultado | Tiempo | Memoria |
---|---|---|---|
#1 |
Correcto
|
0.001 s | 0 KBi |
#2 |
Tiempo límite excedido
|
1.061 s | 83 KBi |
#3 |
Correcto
|
0.012 s | 53 KBi |
#4 |
Correcto
|
0.005 s | 3 KBi |
#5 |
Tiempo límite excedido
|
1.062 s | 20 KBi |
#6 |
Tiempo límite excedido
|
1.062 s | 20 KBi |
#7 |
Tiempo límite excedido
|
1.059 s | 1 KBi |
#8 |
Tiempo límite excedido
|
1.054 s | 4 KBi |
#9 |
Tiempo límite excedido
|
1.068 s | 65 KBi |
#10 |
Tiempo límite excedido
|
1.072 s | 0 KBi |
#11 |
Tiempo límite excedido
|
1.055 s | 1 KBi |
#12 |
Tiempo límite excedido
|
1.1 s | 0 KBi |
#13 |
Correcto
|
0.597 s | 0 KBi |
#14 |
Tiempo límite excedido
|
1.051 s | 0 KBi |
#15 |
Tiempo límite excedido
|
1.064 s | 4 KBi |
#include <bits/stdc++.h> #define REP(i, n) for (int i = 0; i < n; i++) #define pb push_back #define ff first #define ss second #define ii pair<int, int> #define vi vector<int> #define vii vector<ii> #define lli long long int #define fast_io \ ios_base::sync_with_stdio(0); \ cin.tie(0); \ cout.tie(0); using namespace std; ostream &operator<<(ostream &os, const vector<int> &v) { for (auto const &i : v) { os << i << " "; } os << endl; return os; } const int mod = (1e9) + 7; const int N = 1e4 + 1; vi coins; int n; int x; int memo[10005][505]; int dp(int s, int idx) { if (s == x) return 1; if (s > x) return 0; if( idx >= n )return 0; int &ans = memo[s][idx]; if (ans != -1) { ans = 0; // de esta manera todos cada coin se usa seguido una sola vez diferente a la // del for que cuenta cada orden ans += dp(s + coins[idx], idx); // usa el curr idx y manda la dp con el mismo idx ans %= mod; ans += dp(s, idx + 1); // no usa el curr, y manda la dp con el idx que sigue ans %= mod; } else return ans; ans %= mod; return ans; } int main() { fast_io; cin >> n; coins.resize(n); REP(i, n) cin >> coins[i]; int m; cin >> m; REP(i, m) { cin >> x; cout << dp(0, 0) << endl; } return 0; }