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
#include <iostream>
#include <map>

int main() {
    int32_t n;
    std::cin >> n;

    std::map<int64_t, int64_t> energyToLength;
    energyToLength.emplace(0, n);
    int64_t plusEnergy = 0;

    for (int32_t i = 0; i < n; ++i) {
        int64_t a;
        std::cin >> a;

        plusEnergy += a; 

        auto acc = energyToLength.lower_bound(-plusEnergy);
        if (acc != energyToLength.end()) {
            auto pos = energyToLength.insert_or_assign(-plusEnergy, acc->second - 1).first;

            auto unnecessaryStart = pos;
            while (unnecessaryStart != energyToLength.begin()) {
                --unnecessaryStart;
                if (unnecessaryStart->second < pos->second) {
                    ++unnecessaryStart;
                    break;
                }
            }
            energyToLength.erase(unnecessaryStart, pos);
        }
    }

    auto acc = energyToLength.lower_bound(-plusEnergy);
    if (acc != energyToLength.end()) {
        std::cout << acc->second << "\n";
    } else {
        std::cout << "-1\n";
    }
}