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
#include <iostream>
#include <algorithm>
using namespace std;
const int mod = 1e9 + 7;
int a[5010];
int dp[5010 * 5010],n,sum;
int i,j;
long long w;
int main()
{
    ios_base :: sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n; cin >> n;
    for(int i = 0 ; i < n; i++)
        cin >> a[i];
    sort(a, a + n);
    dp[0] = 1;
    for(i = 0 ; i < n; i++){
        if(a[i] <= sum + 1){
            sum += a[i];
        }
        else
            break;
        for(int j = sum; j >= 2 * a[i] - 1; j--){
            w -= dp[j];
            dp[j] = (dp[j] + dp[j - a[i]]) % mod;
            w += dp[j];
        }
    }
    cout << w % mod << '\n';
}