Cod sursa(job #610833)

Utilizator GheorgheMihaiMihai Gheorghe GheorgheMihai Data 29 august 2011 14:21:39
Problema Ghiozdan Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.41 kb
#include <stdio.h>

#include <deque>

using namespace std;

struct vect
{
	int x, nr;
};

int n, g;
int f[202];
int d[3][75002], t[3][75002];

const int inf = 1000000000;

void rez (int st, int dr, int g)
{
	int p, c, i, j, k, x, m = (st + dr) >> 1;
	
	if (!g)
		return;
	if (st == dr)
	{
		for (i = 1; i <= f[st] && i * st <= g; i ++)
			printf ("%d\n", st);
		return;
	}
	
	d[0][0] = 0;
	for (i = 1; i <= g; i ++)
		d[0][i] = inf;
	c = 0;
	
	for (i = st; i <= dr; i ++)
	{
		if (!f[i])
			continue;
		p = c;
		c = !c;
		for (j = 0; j < i; j ++)
		{
			deque < vect > q;
			for (k = j; k <= g; k += i)
			{
				while (!q.empty() && q.front().x < k - f[i] * i)
					q.pop_front();
				while (!q.empty() && q.back().nr > d[p][k] - k / i)
					q.pop_back();
				q.push_back ((vect){k, d[p][k] - k / i});
				if (!q.empty())
				{
					x = q.front().x;
					d[c][k] = d[p][x] + (k - x) / i;
					t[c][k] = i <= m ? k : t[p][x];
				}
			}
		}
	}
	
	for (i = g; i >= 0; i --)
		if (d[c][i] != inf)
			break;
	if (st == 1 && dr == 200)
		printf ("%d %d\n", i, d[c][i]);
	
	rez (st, m, t[c][i]);
	rez (m + 1, dr, g - t[c][i]);
}

int main ()
{
	freopen ("ghiozdan.in", "r", stdin);
	freopen ("ghiozdan.out", "w", stdout);
	
	scanf ("%d %d", &n, &g);
	
	int i, x;
	
	for (i = 1; i <= n; i ++)
	{
		scanf ("%d", &x);
		f[x] ++;
	}
	
	rez (1, 200, g);
	return 0;
}