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

using namespace std;

#define PB push_back
#define MP make_pair
#define F first
#define S second
#define ALL(x) (x).begin(),(x).end()
#define SIZE(x) (int)(x).size()
#define CLEAR(tab) memset(tab, 0, sizeof(tab))
#define REP(x, n) for(int x = 0; x < (n); x++)
#define FOR(x, b, e) for(int x = (b); x <= (e); x++)
#define FORD(x, b, e) for(int x = (b); x >= (e); x--)
#define VAR(v, n) __typeof(n) v = (n)
#define FOREACH(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i)
#define DEBUG(fmt, ...) fprintf(stderr, fmt, ##__VA_ARGS__)

typedef long long int LL;
typedef pair<int,int> PII;
typedef vector<int> VI;

const int MXN = 50010;
const int C = 262144;
const int INF = 1000000001;
const int MOD = 1000000007;

int n, m;
int a[MXN];

void test() {
    scanf("%d %d", &n, &m);
    FOR(i, 1, n)
        scanf("%d", &a[i]);
    
    vector<bool> out(n + 1, 1);
    vector<int> b(n + 1, 0);
    out[n] = 0;
    b[n] = m;

    FORD(i, n - 1, 1) {
        int needed_votes = (n - i) / 2 + 1;
        vector<bool> next_out = out;
        vector<int> next_b = b;
        vector<PII> c;
        int curr_votes = 1;

        FOR(j, i + 1, n)
            if(out[j])
                curr_votes++;
            else
                c.PB(MP(b[j] + a[j], -j));

        if(curr_votes < needed_votes) {
            needed_votes -= curr_votes;
            int paid_amount = 0;
            vector<int> paid_ind;

            sort(ALL(c));
            FOREACH(it, c) {
                if(!needed_votes || paid_amount + (it -> F) > m)
                    break;
                paid_amount += it -> F;
                paid_ind.PB(-(it -> S));
                needed_votes--;
            }

            if(!needed_votes) {
                next_out[i] = 0;
                next_b[i] = m - paid_amount;
                FOR(j, i + 1, n)
                    next_out[j] = next_b[j] = 0;
                FOREACH(it, paid_ind)
                    next_b[*it] = b[*it] + a[*it];
            }
        }
        else {
            next_b[i] = m;
            next_out[i] = 0;
            FOR(j, i + 1, n)
                next_b[j] = next_out[j] = 0;
        }

        out = next_out;
        b = next_b;
    }

    FOR(i, 1, n) {
        if(out[i])
            b[i] = -1;
        printf("%d ", b[i]);
    }
    printf("\n");
}

int main() {
	int te = 1;
	//scanf("%d", &te);
	while(te--)
		test();
	return 0;
}