Northern Grand Prix 2011. Elections (Division 1 Only!)

#include <cstdio>
#include <cmath>

using namespace std;


const int MAXN = 11;
const int MAXS = 55;
const int MAXA = 111;
const long long INF = (long long)1e+15;

int n, s;
int a[MAXN][MAXA];
int v[MAXN];
int upd[MAXA], cnt;
long long V;

long long f[MAXN][MAXS][MAXA][MAXA];
int p[MAXN][MAXS][MAXA][MAXA];


long long abs(long long x)
{
    return x < 0? -x : x;
}

int rec(int i, int j, int k, int l)
{
    if (i == 0) return 0;

    int x = p[i][j][k][l];
    rec(i - 1, j - a[i - 1][x], k - x, l);

    printf("%d\n", x);
    return 0;
}

int main()
{
    freopen("elections.in", "r", stdin);
    freopen("elections.out", "w", stdout);

    cnt = V = 0;

    scanf("%d %d", &n, &s);
    for (int i = 0; i < n; i++)
    {
        cnt++;

        scanf("%d", &v[i]);
        V += v[i];

        int m;
        scanf("%d", &m);
        for (int j = 0; j < m; j++)
        {
            int x;
            scanf("%d", &x);
            if (x < MAXA) upd[x] = cnt;
        }

        for (int j = 1; j < MAXA; j++)
            a[i][j] = a[i][j - 1] + (upd[j] != cnt);
/*
        for (int j = 0; j < MAXA; j++)
            printf("%d ", a[i][j]);
        printf("\n");
//*/
    }

    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= s; j++)
            for (int k = 0; k < MAXA; k++)
                for (int l = 0; l < MAXA; l++)
                    f[i][j][k][l] = INF;

    for (int i = 0; i < MAXA; i++)
        f[0][0][0][i] = 0;

    for (int i = 0; i < n; i++)
        for (int j = 0; j <= s; j++)
            for (int k = 0; k < MAXA; k++)
                for (int l = 0; l < MAXA; l++)
                    if (f[i][j][k][l] < INF)
                    {
                        for (int x = 0; j + a[i][x] <= s && k + x < MAXA ; x++)
                        {
                            int I = i + 1;
                            int J = j + a[i][x];
                            int K = k + x;
                            int L = l;

                            long long value = abs(x * V - v[i] * L);

                            if (f[I][J][K][L] >= f[i][j][k][l] + value)
                            {
                                f[I][J][K][L] = f[i][j][k][l] + value;
                                p[I][J][K][L] = x;
                            }
                        }
                    }

    int x = 1;
    for (int i = 1; i < MAXA; i++)
        if (f[n][s][i][i] * x < f[n][s][x][x] * i)
            x = i;

    rec(n, s, x, x);
    return 0;
}