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
157
158
159
160
161
#include <stdio.h>

#define L long int

L el[500001];

struct przedzial { 
//    L start; // gdzie sie zaczal ten przedzial (nie wiem, czy to potrzebne) 
    L ostatni_konieczny; // gdzie musi sie ten przedzial skonczyc, nie moze wczesniej
    L koszt; // to jest koszt tego przedzialut
    L wartosc; // wartosc pradu
    L potencjal; // to jest jego potencjal, czyli tyle ile moze dodac od ostatniego koniecznego, gdybysmy chcieli go aktualizowac
    
    przedzial() {
    }
    
    przedzial(L k, L w, L p) {
       // printf("dodaje przedzial koszt %d wartosc %d konieczny %d\n", k, w, p);
        this->koszt = k;
        this->wartosc = w;
        this->ostatni_konieczny = p;
        this->potencjal = 0;
    }
};


przedzial przedzialy[500010]; // o tyle ich jest
L przedzialow;


void dodaj_przedzial(L koszt, L wartosc, L pozycja)  {
    przedzialy[przedzialow++] = przedzial(koszt, wartosc, pozycja);
}

void pisz_przedzialy() {
    printf("----------------\n");
    for(L i=0;i<przedzialow;i++) {
        przedzial *p = przedzialy+i;
        printf("koszt %5ld   wartosc %5ld pozycja wazna %5ld  potencjal %5ld\n", 
            p->koszt,
            p->wartosc,
            p->ostatni_konieczny,
            p->potencjal);
    }
    printf("----------------\n");
}

void aktualizuj_przedzialy(L pozycja, L wartosc) { 
    //printf("analuzuje %d %d\n", pozycja, wartosc);
    if (wartosc == 0) return; // pole nas nie interesuje
    if (wartosc < 0) { // to jest fabryka
        // fabryki sa super, bo latwo sie z nimi rozprawic.
        // analzujemy kazdy przedzial


        // przedzialy ujemne
        for(L i=0;i<przedzialow;i++) {
            przedzial *p = przedzialy+i;
            if (p->wartosc < 0) { // jesli przedzial jest ujemny, to sprawa jest banalna - napotkalismy fabryke podlaczamy ja pod przedzial
                p->wartosc += wartosc; // !!dodajemy ujemna wartosc fabryki
            }
        } // robia sie jeszcze bardziej ujemne
        // wybieram najtanszy jakis
        L kosztnowego = 1000000;
        for(L i=0;i<przedzialow;i++) {
            przedzial *p = przedzialy+i;
            if (p->wartosc >= 0 && p->koszt < kosztnowego) { // jesli przedzial jest ujemny, to sprawa jest banalna - napotkalismy fabryke podlaczamy ja pod przedzial
                kosztnowego = p->koszt; // to mi poszluzy do utowrzenia nowego przedzialu
            }
        } // to sobie zapisuje zeby dodac na podstawie tych wartosci

        // ok, jesli zamkne przedzaialy przed fabryka to jedno 
        // ale moge ich nie zamykac przedd fabryka tylko moge je do fabryki dociagnac
        // jak je dociagne do fabryki, to wtedy juz musze je ciagnac dalej        
        for(L i=0;i<przedzialow;i++) {
            przedzial *p = przedzialy+i;
            if (p->wartosc >= 0) { 
                p->koszt+= pozycja - p->ostatni_konieczny; // zwiekszam mu koszt
                p->ostatni_konieczny = pozycja; // musi byc do tego miejsca
                p->wartosc += wartosc; // zmniejszam mu wartosc o ta fabryke
                p->wartosc += p->potencjal; // zwiekszam mu potencjal o elektrownie ktore staly na jego drodze
                p->potencjal = 0;
            }
        } // to jest dodatnie
        
        if (przedzialow == 0) { // nie ma przedzialow  a jest fabryka
            dodaj_przedzial(0, wartosc, pozycja); // ot taki przedzial
            
        } else {    
            // na koniec dodaje nowy przedzial
            dodaj_przedzial(kosztnowego, wartosc, pozycja); ///! Wartosc jest ujemna!
        }
    } else { // to jest elektrownia
    
        if (przedzialow == 0) { // nie ma przedzialow 
            dodaj_przedzial(0, wartosc, pozycja); // ! pierwsza elektrownia
        } else {
        
            L minkoszt = 1000000;

            for(L i=0;i<przedzialow;i++) {
                przedzial *p = przedzialy+i;
                if (p->wartosc >= 0) { // przedzialy sa dodatnie, nic sie nie zmienia, zwieksza sie  ich potencjal
                    if (p->koszt < minkoszt) { // ot mozemy zakonczyc
                        minkoszt = p->koszt;
                    }
                    p->potencjal += wartosc;
                } else { // dobrze - przedzialy jest ujemny, to i tak nie mozemy go zakonczyc
                    p->wartosc += wartosc; // zwiekszzamy jego wartosc
                    p->koszt += pozycja - p->ostatni_konieczny; // zwiekszamy mu koszt
                    p->ostatni_konieczny = pozycja; // no bez nas ani nawet
                    p->potencjal = 0; // ten przedzial nie ma potencjalu
                }
            }
            dodaj_przedzial(minkoszt, wartosc, pozycja); // ! pierwsza elektrownia
            
        }        
    }
    //pisz_przedzialy();
}


L minimalna(L n, L *el) {

    // dobra, tutaj  sprawa jest prosta -czyli lecim z koksem
    przedzialow = 0;
    for(L i=0;i<n;i++) {
        aktualizuj_przedzialy(i, el[i]);
    }
    L koszt = 1000000;
    for(L i=0;i<przedzialow;i++) {
        if (przedzialy[i].wartosc >=0 && przedzialy[i].koszt < koszt) {
            koszt = przedzialy[i].koszt;
        }
    }
    
    if (koszt > 500001) { // nie da sie, ale tutaj nie wejdziemy
        return -1;
    }
    return koszt;
}

int main() {
    L n, rv; // ilosc miast
    L r = scanf("%ld\n", &n);
//    L sum = 0;
    L sum = 0L;
    L v;
    for(L i=0;i<n;i++) {
        L b = scanf("%ld ", &v);
        el[i] = v;
        sum += el[i];
    }  
    if (sum < 0) { // jesli suma jest mniejsza, no to w tym momencie nie musimy w ogole sie tym martwic
        printf("-1\n");
        return 0;
    }
    rv = minimalna(n, el);
    printf("%ld\n", rv);
    return 0;
}