#include <bits/stdc++.h> const int B = 5005 * 5005; const int M = 1000000007; using namespace std; int n, t[5005], dp[B], sum, res, goleft[B * 2]; void maxuj(int x, int y) { //cout << __func__ << "(" << x << " " << y << ")\n"; x += B; while(x > 0) { goleft[x] = max(goleft[x], y); x >>= 1; } } int dajmax(int x) { x += B; int res = goleft[x]; x++; while(x > 1) { if(x % 2 == 1) res = max(res, goleft[x - 1]); x >>= 1; } return res; } int32_t main() { ios_base::sync_with_stdio(0); cin >> n; for(int i = 1; i <= n; i++) { //t[i] = (1 << min(i, 12)); cin >> t[i]; sum += t[i]; } sort(t + 1, t + n + 1); dp[0] = 1; for(int i = 1; i <= n; i++) { if(t[i] == 1) { for(int j = i; j >= 1; j--) { dp[j] += dp[j - 1]; if(dp[j] >= M) dp[j] -= M; } maxuj(i + 1, i); } else { int ostatnie = 0; int j = dajmax(sum + 1); //cout << i << " " << j << "\n"; while(j >= t[i] - 1) { // cout << j << " " << dajmax(j) << "\n"; dp[j + t[i]] += dp[j]; maxuj(j + t[i] + 1, j + t[i]); if(dp[j + t[i]] >= M) dp[j + t[i]] -= M; if(j == 1) break; j = dajmax(j); } } //for(int i =1; i <= sum; i++) cout << dp[i] << " "; // cout << "\n"; } for(int i = 1; i <= sum; i++) { res += dp[i]; if(res >= M) res -= M; } cout << res << "\n"; }
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 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 | #include <bits/stdc++.h> const int B = 5005 * 5005; const int M = 1000000007; using namespace std; int n, t[5005], dp[B], sum, res, goleft[B * 2]; void maxuj(int x, int y) { //cout << __func__ << "(" << x << " " << y << ")\n"; x += B; while(x > 0) { goleft[x] = max(goleft[x], y); x >>= 1; } } int dajmax(int x) { x += B; int res = goleft[x]; x++; while(x > 1) { if(x % 2 == 1) res = max(res, goleft[x - 1]); x >>= 1; } return res; } int32_t main() { ios_base::sync_with_stdio(0); cin >> n; for(int i = 1; i <= n; i++) { //t[i] = (1 << min(i, 12)); cin >> t[i]; sum += t[i]; } sort(t + 1, t + n + 1); dp[0] = 1; for(int i = 1; i <= n; i++) { if(t[i] == 1) { for(int j = i; j >= 1; j--) { dp[j] += dp[j - 1]; if(dp[j] >= M) dp[j] -= M; } maxuj(i + 1, i); } else { int ostatnie = 0; int j = dajmax(sum + 1); //cout << i << " " << j << "\n"; while(j >= t[i] - 1) { // cout << j << " " << dajmax(j) << "\n"; dp[j + t[i]] += dp[j]; maxuj(j + t[i] + 1, j + t[i]); if(dp[j + t[i]] >= M) dp[j + t[i]] -= M; if(j == 1) break; j = dajmax(j); } } //for(int i =1; i <= sum; i++) cout << dp[i] << " "; // cout << "\n"; } for(int i = 1; i <= sum; i++) { res += dp[i]; if(res >= M) res -= M; } cout << res << "\n"; } |