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
#include <cstdio>
#include <iostream>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>


using namespace std;
 
int main()
{
    int n;
    scanf("%d",&n);
    int t[n], path[n];
    long long int sum = 0;

    for (int i=0;i<n; i++)
    {
        scanf("%d",&t[i]);
        sum+=t[i];
        path[i] = 0;
    }
    if (sum < 0)
    {
        printf("%d\n",-1);
        return 0;
    }




    bool atLeastOneFactory = true;

    while (atLeastOneFactory)
    {
        int maxFactory = -1;
        int maxDistance = 0;
        int maxElectricityI = -1;

        atLeastOneFactory = false;
        for (int i=0;i<n; i++)
        {
            if (t[i] < 0) //factory
            {
                atLeastOneFactory = true;
                for (int j=0; i+j<n||i-j>=0;j++)
                {
                    if (i+j < n && t[i+j] > 0)
                    {
                        if (maxDistance < j)
                        {
                            maxDistance = j;
                            maxElectricityI = i+j;
                            maxFactory = i;
                        }
                        break;
                    }
                    if (i-j>=0 && t[i-j] > 0)
                    {
                         if (maxDistance < j)
                         {
                             maxDistance = j;
                             maxElectricityI = i-j;
                             maxFactory = i;
                         }
                         break; 
                    }
                }
            }
        }

        for (int i=min(maxFactory, maxElectricityI); i<max(maxFactory, maxElectricityI); i++)
            path[i] = 1;

        if (t[maxFactory] > t[maxElectricityI])
        {
            t[maxFactory] += t[maxElectricityI];
            t[maxElectricityI] = 0;
        }
        else
        {
            t[maxElectricityI] += t[maxFactory];
            t[maxFactory] = 0;   
        }
        //for (int i=0; i<n; i++)
        //    printf("%d",t[i]);
        //printf("\n");
    }

    int result = 0;
    for (int i=0; i<n; i++)
    {
        //printf("%d",path[i]);
        if (path[i] > 0)
            result++;
    }

    printf("%d\n", result);
}