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 <cassert>
#include <cstdint>
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

typedef int32_t i32;
typedef int64_t i64;

const i32 KOSZT_NA = INT32_MAX;

struct Miasto {
    i32 kosztOdPoprzedniego;
    i32 energia;
    i32 koszt;
};

int main()
{
    std::ios::sync_with_stdio(false);

    i32 n;
    std::cin >> n;

    std::vector<Miasto> miasta;
    miasta.reserve(n);

    i64 sumaEn = 0;
    i32 poprz = 0;
    for (i32 i = 0; i < n; i++) {
        i32 a;
        std::cin >> a;
        if (a != 0) {
            Miasto m;
            m.kosztOdPoprzedniego = i - poprz;
            m.energia = a;
            m.koszt = KOSZT_NA;
            miasta.push_back(m);
            poprz = i;
            sumaEn += a;
        }
    }
    miasta[0].kosztOdPoprzedniego = 0;

    if (sumaEn < 0) {
        std::cout << "-1\n";
        return 0;
    }

    i32 m = miasta.size();

    for (i32 i = m - 1; 0 <= i; i--) {
        i32 koszt = 0;
        i64 en = miasta[i].energia;
        for (i32 j = i + 1; j < m; j++) {
            if (en >= 0) {
                // i..j-1 zaspokaja energię. Sprawdźmy zakończenie linii tutaj
                if (miasta[j].koszt != KOSZT_NA) {
                    i32 razem = koszt + miasta[j].koszt;
                    if (razem < miasta[i].koszt)
                        miasta[i].koszt = razem;
                }
            }
            // kontynuujmy z linią i..j
            koszt += miasta[j].kosztOdPoprzedniego;
            en += miasta[j].energia;

            // juz lepiej nie bedzie: wyskakujemy.
            if (koszt >= miasta[i].koszt)
                break;
        }
        if (en >= 0 && koszt < miasta[i].koszt)
            miasta[i].koszt = koszt;
    }

    i32 wynik = miasta[0].koszt;
    if (wynik == KOSZT_NA)
        wynik = -1;
    std::cout << wynik << '\n';
    return 0;
}