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
72
73
74
75
76
77
78
79
80
81
82
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>

using namespace std;

typedef long long LL;

map<LL, int> le, mpr;

int main()
{

    ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int nn, aa[500];
    cin>>nn;
    for (int i=0; i<nn; ++i)
        cin>>aa[i];

    int n=nn*(nn+1)/2;
    LL a[200000], mil[200000], mal[200000], mip[200000], map[200000];
    for (int q=0, p=0; p<nn; ++p)
    {
        LL s=0;
        for (int k=p; k<nn; ++k, ++q)
        {
            s+=aa[k];
            a[q]=s;
        }
    }
    sort(a, a+n);

    mil[0]=mal[0]=a[0];
    for (int i=1; i<n; ++i)
    {
        mil[i]=min(mil[i-1], a[i]);
        mal[i]=max(mal[i-1], a[i]);
    }

    mip[n-1]=map[n-1]=a[n-1];
    for (int i=n-2; 0<=i; --i)
    {
        mip[i]=min(mip[i+1], a[i]);
        map[i]=max(map[i+1], a[i]);
    }


    LL wyn=0;

    for (int i=1; i<n; ++i)
        ++mpr[-a[i]];
    ++le[a[0]];
    for (int i=1; i<n-1; ++i)
    {
        LL z=a[i];
        if (--mpr[-z]==0)
            mpr.erase(-z);
        for (auto il=le.begin(); il!=le.end(); )
        {
            LL mbpr=-il->first-z;
            auto ip=mpr.lower_bound(-mbpr);
            if (ip==mpr.end())
                break;
            if (ip->first==-mbpr)
            {
                wyn+=((LL) il->second)*ip->second;
                ++il;
            }
            else
            {
                il=le.lower_bound(ip->first-z);
            }
        }
        ++le[z];
    }

    cout<<wyn;
    return 0;
}