#include <bits/stdc++.h> using namespace std; long long dp[5010], duze = 0; const long long p = 1000000007; int main() { std::ios_base::sync_with_stdio(false); cin.tie(NULL); dp[0] = 1; int n; cin >> n; int tab[n]; for(int i = 0; i < n; i ++) cin >> tab[i]; sort(tab, tab + n); for(int i = 0; i < n; i ++) { long long x = tab[i]; duze = (duze * 2) % p; for(int k = 5009; k >= 0; k --) { if(x <= k + 1) { if(k + x >= 5010) { duze += dp[k]; duze = duze % p; } else { dp[k + x] += dp[k]; dp[k + x] = dp[k + x] % p; } } } } long long wynik = 0; for(int i = 1; i < 5010; i ++) wynik = (wynik + dp[i]) % p; wynik = (wynik + duze) % p; cout << wynik; return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 | #include <bits/stdc++.h> using namespace std; long long dp[5010], duze = 0; const long long p = 1000000007; int main() { std::ios_base::sync_with_stdio(false); cin.tie(NULL); dp[0] = 1; int n; cin >> n; int tab[n]; for(int i = 0; i < n; i ++) cin >> tab[i]; sort(tab, tab + n); for(int i = 0; i < n; i ++) { long long x = tab[i]; duze = (duze * 2) % p; for(int k = 5009; k >= 0; k --) { if(x <= k + 1) { if(k + x >= 5010) { duze += dp[k]; duze = duze % p; } else { dp[k + x] += dp[k]; dp[k + x] = dp[k + x] % p; } } } } long long wynik = 0; for(int i = 1; i < 5010; i ++) wynik = (wynik + dp[i]) % p; wynik = (wynik + duze) % p; cout << wynik; return 0; } |