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
#include <iostream>
#include <sstream>
#include <map>
#include <set>
using namespace std;

multimap<short int,short int> opakowania;
map<short,int> memo;

int kick_it (const multimap<short int,short int>::iterator it, short int suma/*, short int idx*//*, map<short,int> memo*/) {
    int podsuma = 0;

    if (it == opakowania.end()) return 0;

    if (it->first > suma+1) {
        //cout << "memo insert1: " << ' ' << it->second << ' ' << podsuma << ' ' << '\n';
        memo.insert(make_pair(it->second,0));
        return 0;
    } else {
        multimap<short int,int>::iterator memo_it = memo.find(it->second);
        if ( memo_it != memo.end() ) {
            //cout << "memo: " << ' ' << memo_it->first << ' ' << memo_it->second << ' ' << '\n';
        return memo_it->second;
        } else{
            //cout << "no memo: " << it->second << '\n';
        }


        podsuma++;
        suma += it->first;
        map<short int,short int>::iterator itr = it;++itr;
        for (; itr!=opakowania.end(); ++itr) {
            //cout << it->first << " ---->: " << itr->first << " " << "suma: " << suma << " podsuma: " << podsuma << '\n';
            podsuma += kick_it(itr,suma/*,++idx*//*,memo*/);
            //cout << it->first << " <----: " << itr->first << " " << "podsuma: " << podsuma << '\n';
            if (podsuma >= 1000000007) {
                podsuma -= 1000000007;
            }
        }

    }
    //cout << "memo insert2: " << ' ' << it->second << ' ' << podsuma << ' ' << '\n';
    memo.insert(make_pair(it->second,podsuma));
    return podsuma;

}


main (int arc, char ** argv) {

    int n = 0;
    cin >> n;
    //cout << "n:  " << n << '\n';

    for (short int i = 0; i < n; i++)
    {
        short int ai;
        cin >> ai;
        //cout << "ai:" << ai << '\n';
        opakowania.insert(make_pair(ai,i));
    }
    //cout << "opakowania.size(): " << opakowania.size() << '\n';
    map<short int,int> memo;
    cout << kick_it(opakowania.begin(), 0/*, 1*//*, memo*/) << '\n';

    return 0;
}