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
#include <bits/stdc++.h>

using namespace std;


long long w_prawo=0, w_lewo=0, mini;
long long wynik1=0, wynik2=0;
long long pref[500003];
vector <long long> fabryki;
int n;
int main () {

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



    cin>>n;

    long long tab[n+1], tab1[n+1], tab2[n+1], temp[n+1];
    pref[0]=0;
    for (int i=1; i<=n; i++) {
        cin>>tab[i];
        tab1[i]=tab[i];
        tab2[i]=tab[i];
        pref[i]=pref[i-1]+tab[i];

        if (tab[i]<0)
            fabryki.push_back(i); }

    if (pref[n]<0) {
        cout<<"-1";
        return 0; }



    for (int jklm=0; jklm<fabryki.size(); jklm++) {
        w_prawo=0;
        w_lewo=tab1[fabryki[jklm]];

        for (int i=fabryki[jklm]-1; i>=0; i--) {
                w_lewo+=tab1[i];
                temp[i]=w_lewo; }

        for (int i=fabryki[jklm]; i<=n; i++) {
            w_prawo+=tab1[i];
            temp[i]=w_prawo; }

        mini=INT_MAX;
        int jakie_i;

        for (int i=1; i<=n; i++)  {
            if (temp[i]>=0) {
                if (mini>=abs(fabryki[jklm]-i)) {
                    mini=abs(fabryki[jklm]-i);
                    jakie_i=i; } } }

        long long sumka=0;
        if (jakie_i>fabryki[jklm]) {
             for (int i=fabryki[jklm]; i<=jakie_i; i++){
                sumka+=tab1[i];
                if (tab1[i]>0 && sumka<=0)
                    tab1[i]=0;
                else
                    tab1[i]=tab1[i]-sumka;   } }

        else if (jakie_i<fabryki[jklm]) {
            for (int i=fabryki[jklm]; i>=jakie_i; i--){
                sumka+=tab1[i];
                if (tab1[i]>0 && sumka<=0)
                    tab1[i]=0;
                else if (tab1[i]>0)
                    tab1[i]=tab1[i]-sumka;  } }

        wynik1+=mini;  }

    for (int jklm=fabryki.size()-1; jklm>=0; jklm--) {
            long long w_prawo=0;
            long long w_lewo=tab2[fabryki[jklm]];

            for (int i=fabryki[jklm]-1; i>0; i--) {
                w_lewo+=tab2[i];
                temp[i]=w_lewo; }

            for (int i=fabryki[jklm]; i<=n; i++) {
                w_prawo+=tab2[i];
                temp[i]=w_prawo; }


            long long mini=INT_MAX;
            int jakie_i;

            for (int i=1; i<=n; i++)  {
                if (temp[i]>=0) {
                    if (mini>abs(fabryki[jklm]-i)) {
                        mini=abs(fabryki[jklm]-i);
                        jakie_i=i; } } }

            long long sumka=0;
            if (jakie_i>fabryki[jklm]) {
                for (int i=fabryki[jklm]; i<=jakie_i; i++){
                    sumka+=tab2[i];
                    if (tab2[i]>0 && sumka<=0)
                        tab2[i]=0;
                    else
                        tab2[i]=tab2[i]-sumka; } }

            else if (jakie_i<fabryki[jklm]) {
                for (int i=fabryki[jklm]; i>=jakie_i; i--){
                    sumka+=tab2[i];
                    if (tab2[i]>0 && sumka<=0)
                        tab2[i]=0;
                    else
                        tab2[i]=tab2[i]-sumka;  } }

            wynik2+=mini;  }


        cout<<min(wynik1,wynik2);

}