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

using namespace std;

typedef long long I;

#define D(x) 


I prad_suma = 0, koszt_suma = 0;

#define IMAX (2LL*524288LL*1000000000LL)
#define MAX 524288

//#define MAX 32
//#define IMAX 100

I K[MAX*3];

void print()
{
    int j=1;
    for(int i=0;i<7;i++) {
        for(;j<(1<<i);j++) cout << K[j] + prad_suma << " ";
        cout << "\n";
    }
    cout << "-------------\n";
}

void correct(int a) {
    if (a == 0) return;
    K[a] = max(K[2*a], K[2*a+1]);
    return correct(a/2);
}

void _insert(I prad, int koszt) {
    if (K[koszt+MAX] < prad) {
        K[koszt+MAX] = prad;
        correct((koszt+MAX)/2);
    }
}

void insert(I prad, int koszt) {
    D(cout << "insert p:" << prad << " k:" << koszt << " (" << prad - prad_suma << "," << koszt_suma - koszt << ")\n");
    _insert(prad - prad_suma, koszt_suma - koszt);
}


int find(I prad, int p = 1) {
    if(K[p] + prad >=0) {
        D(cout << "f:" << p <<  "(" << K[p] << ")\n");
        if(p>=MAX) return koszt_suma - (p-MAX);
        if(K[2*p+1] + prad >=0) return find(prad, 2*p+1);
        return find(prad, 2*p);
    }
    return -1;
}


int main()
{
    for(int i = 0 ;i < 2 * MAX; i++) K[i] = -IMAX;

    I n, a;
    cin >> n;
    cin >> a;
    insert(a, 0);
    D(print());
    while(--n) {
        cin >> a;
        auto k = find(prad_suma);
        D(cout << "a:" << a << " wyc k:" << k << "\n");
        prad_suma += a;
        koszt_suma += 1;
        if(k>=0) insert(a, k);
        D(print());
    }
    auto k = find(prad_suma);
    cout << k << "\n";
}