#include <cstdio> #include <algorithm> using namespace std; long long int sumy[5000 * 5000]; long long int p = 1000000007l; int main() { int n; scanf("%d", &n); long long int a[n]; for (int i = 0; i < n; i++) { scanf("%lld", &a[i]); } sort(a, a + n); sumy[0] = 1l; long long int max_suma = 0; for (int i = 0; i < n; i++) { for (int j = max_suma + a[i]; j >= 2 * a[i] - 1; j--) { sumy[j] = (sumy[j] + sumy[j - a[i]]) % p; if (j > max_suma) { max_suma = j; } } } long long int wynik = 0; for (int i = 1; i <= max_suma; i++) { wynik = (wynik + sumy[i]) % p; } printf("%lld", 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 36 37 38 39 40 41 | #include <cstdio> #include <algorithm> using namespace std; long long int sumy[5000 * 5000]; long long int p = 1000000007l; int main() { int n; scanf("%d", &n); long long int a[n]; for (int i = 0; i < n; i++) { scanf("%lld", &a[i]); } sort(a, a + n); sumy[0] = 1l; long long int max_suma = 0; for (int i = 0; i < n; i++) { for (int j = max_suma + a[i]; j >= 2 * a[i] - 1; j--) { sumy[j] = (sumy[j] + sumy[j - a[i]]) % p; if (j > max_suma) { max_suma = j; } } } long long int wynik = 0; for (int i = 1; i <= max_suma; i++) { wynik = (wynik + sumy[i]) % p; } printf("%lld", wynik); return 0; } |