Pagini recente » Cod sursa (job #774963) | Cod sursa (job #1525113) | Cod sursa (job #2461518) | Cod sursa (job #1072071) | Cod sursa (job #507826)
Cod sursa(job #507826)
#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]);
}