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
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
#include <bits/stdc++.h>
using namespace std;

int main()
{
    bool czy=1;
    int n;
    cin>>n;
    vector<pair<int,int> > v;
    for(int i=0; i<n; i++)
    {
        int c;
        cin>>c;
        v.push_back(make_pair(c, i));

    }
    int sum=0;
    for(int i=0; i<v.size(); i++)
    {
        if(v[i].first<0)
        {
            vector<pair<int,int> > L;
            L.push_back(make_pair(0,0));
            int j=i-1;
            while(j>=0)
            {
                L.push_back(make_pair(L[L.size()-1].first+v[j].first, i-j));
                if(L[L.size()-1].first>=v[i].first*-1)
                    j=-1;
                j--;
            }
            vector<pair<int,int> > P;
            P.push_back(make_pair(0,0));
            j=i+1;
            while(j<v.size())
            {
                P.push_back(make_pair(P[P.size()-1].first+v[j].first, j-i));
                if(P[P.size()-1].first>=v[i].first*-1)
                    j=v.size();
                j++;
            }
            int po=1 , ko=L.size()-1;
            int mis=INT_MAX;
            int l=-1,p=-1;
            if(L[ko].first>=v[i].first*-1)
            {
                l=L.size()-1;
                mis=L[ko].second;
            }
            for(int yy=po; yy<P.size(); yy++)
            {
                if(L[ko].first+P[yy].first>=v[i].first*-1 && L[ko].second+P[yy].second<mis)
                {
                    l=ko;
                    p=yy;
                    mis=L[ko].second+P[yy].second;
                }
            }
            po=P.size()-1;
            for(int yy=ko; yy>0; yy--)
            {
                if(L[yy].first+P[po].first>=v[i].first*-1 && L[yy].second+P[po].second<mis)
                {
                    l=yy;
                    p=po;
                    mis=L[yy].second+P[po].second;
                }
            }
            if(P[P.size()-1].first>=v[i].first*-1 && P[P.size()-1].second<=mis)
            {
                l=-1;
                p=1;
                mis=P[P.size()-1].second;
            }
            int sub=v[i].first*-1;
            if(mis==INT_MAX)
            {
                cout<<-1;
                i=v.size();
                czy=0;
            }
            else if(p==-1)
            {
                for(int z=l; z>0; z--)
                {
                    v[i-L[z].second].second=v[i].second;
                    if(v[i-L[z].second].first<=sub && v[i-L[z].second].first!=0)
                    {
                        sub-=v[i-L[z].second].first;
                        v[i-L[z].second].first=0;
                    }
                    else if(v[i-L[z].second].first!=0)
                    {
                        v[i-L[z].second].first-=sub;
                        v[i].first=v[i-L[z].second].first;
                        v[i-L[z].second].first=0;
                    }
                }
            }
            else if(p==1 && l==-1)
            {
                for(int z=p; z<P.size(); z++)
                {
                    v[P[z].second+i].second=v[i].second;
                    if(v[P[z].second+i].first<=sub && v[P[z].second+i].first!=0)
                    {

                        sub-=v[P[z].second+i].first;
                        v[P[z].second+i].first=0;
                    }
                    else if(v[P[z].second+i].first!=0)
                    {
                        v[P[z].second+i].first-=sub;
                    }
                }
            }
            else
            {
                for(int z=l; z>0; z--)
                {
                    v[i-L[z].second].second=v[i].second;
                    if(v[i-L[z].second].first<=sub && v[i-L[z].second].first!=0)
                    {
                        sub-=v[i-L[z].second].first;
                        v[i-L[z].second].first=0;
                    }
                    else if(v[i-L[z].second].first!=0)
                    {
                        v[i-L[z].second].first-=sub;
                        v[i].first=v[i-L[z].second].first;
                        v[i-L[z].second].first=0;
                    }
                }
                for(int z=p; z<P.size(); z++)
                {
                    v[P[z].second+i].second=v[i].second;
                    if(v[P[z].second+i].first<=sub && v[P[z].second+i].first!=0)
                    {

                        sub-=v[P[z].second+i].first;
                        v[P[z].second+i].first=0;
                    }
                    else if(v[P[z].second+i].first!=0)
                    {
                        v[P[z].second+i].first-=sub;
                    }
                }
            }
            sum+=mis;

        }

    }
    if(czy)
    cout<<sum;
}