Pagini recente » Cod sursa (job #573788) | Cod sursa (job #2031632) | Cod sursa (job #1821558) | Cod sursa (job #2466256) | Cod sursa (job #610833)
Cod sursa(job #610833)
#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;
}