Cod sursa(job #507826)

Utilizator antoanelaAntoanela Siminiuc antoanela Data 6 decembrie 2010 21:32:27
Problema Ghiozdan Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <cstdio>
#define nmax 20010
#define gmax 75010
#define inf 100000

int n, g, ll, v[nmax], f[210], d[2][gmax], q[gmax], p[gmax], gm[2][gmax], sol[nmax], h;

void solve(int e, int l, int g)
{
	if (!g) return;
	int i, j, st, dr, idx, pr, k, m;
	if (e==l) 
	{
		for (i=1; i<=f[l] && i*l<=g; i++) 
			sol[++h]=l;
		return;
	}
	m=(e+l)/2;
	for (i=1; i<=g; i++) d[0][i]=inf;
	idx=0;
	for (i=e; i<=l; i++)
	{
		if (f[i])
		{
			pr=idx;
			idx=!idx;
			for (j=0; j<i; j++)
			{
				st=1;
				dr=0;
				for (k=j; k<=g; k+=i)
				{
					while (st<=dr && p[st]<k-f[i]*i) st++;
					while (dr>=st && d[pr][k]-(k/i)<=q[dr]) dr--;
					q[++dr]=d[pr][k]-(k/i);
					p[dr]=k;
					if (st<=dr)
					{
						d[idx][k]=d[pr][p[st]]+(k-p[st])/i;
						if (i<=m) gm[idx][k]=k; else gm[idx][k]=gm[pr][p[st]];
					}
				}
			}
		}
	}
	for (i=g; i>=0 && d[idx][i]>=inf; i--);
	if (e==1 && l==ll)
		printf("%d %d\n",i,d[idx][i]);
	solve(e, m, gm[idx][i]);
	solve(m+1, l, g-gm[idx][i]);
}
	

int main()
{
	freopen("ghiozdan.in","r",stdin);
	freopen("ghiozdan.out","w",stdout);
	scanf("%d %d",&n,&g);
	int i;
	for (i=1; i<=n; i++) 
	{
		scanf("%d",&v[i]);
		if (v[i]>ll) ll=v[i];
		f[v[i]]++;
	}
	solve(1, ll, g);
	for (i=1; i<=h; i++) printf("%d\n",sol[i]);
}