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
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;


int main(){
    int n;
    scanf("%d", &n);
    vector<int> cuksy(n);
    vector<int> tmp(5002);
    int mod = 1000000007;
    tmp[0] = 1; // ile juz znalezlismy podzbiorow paczek o zadanej lacznej wartosci
    for(int i=0; i<n; i++)
	    scanf("%d", &cuksy[i]);//musza byc dodatnie wartosci inaczej lipa
    sort(cuksy.begin(), cuksy.end());
    int max_cur = 0;
    for (int i=0; i<n; i++){
	//printf("%d\n", cuksy[i]);
	bool if_break = true;
	for(int j=max_cur; j >= cuksy[i] - 1; j--){
	    if (tmp[j] > 0)
		if_break = false;
	    else
		continue;
	    //printf("%d\n", j + cuksy[i]);
	    if ( j + cuksy[i] > 5000)
		tmp[5001] = (tmp[5001] + tmp[j]) % mod;
	    else
		tmp[j + cuksy[i]] = (tmp[j] + tmp[j + cuksy[i]]) % mod;	
        }
	if (if_break)
	    break;
        max_cur = min(cuksy[i] + max_cur, 5001);


    }
    int suma = -1;
    for(int cuk: tmp)
	suma = (suma + cuk) % mod ;
    printf("%d\n", suma);
    return 0;
}