Pagini recente » Cod sursa (job #1886843) | Cod sursa (job #2145909) | Cod sursa (job #1838315) | Cod sursa (job #2565055) | Cod sursa (job #1290819)
#include <fstream>
#include <deque>
#include <cstring>
using namespace std;
const int kMaxG = 75005, kInf = 0x3f3f3f3f;
ifstream fin("ghiozdan.in");
ofstream fout("ghiozdan.out");
int N, G, a[205], dp[2][kMaxG], up[2][kMaxG];
deque<pair<int, int>> dq;
void Solve(int l, int r, int w) {
if (!w)
return;
if (l == r) {
for (int i = 0; i < a[l] && i * l < w; ++i)
fout << l << "\n";
return;
}
int m = (l + r) >> 1;
memset(dp[0], kInf, sizeof dp[0]);
dp[0][0] = 0;
for (int i = l; i <= r; ++i) {
if (!a[i])
continue;
for (int j = 0; j < i; ++j) {
dq.clear();
for (int k = j; k <= w; k += i) {
int crtv = dp[0][k] - k / i;
while (!dq.empty() && dq.front().first < k - i * a[i])
dq.pop_front();
while (!dq.empty() && dq.back().second >= crtv)
dq.pop_back();
dq.push_back(make_pair(k, crtv));
if (!dq.empty()) {
int crt = dq.front().first;
dp[1][k] = dp[0][crt] + (k - crt) / i;
up[1][k] = (i <= m) ? k : up[0][crt];
}
}
}
memcpy(dp[0], dp[1], sizeof dp[0]);
memcpy(up[0], up[1], sizeof up[0]);
}
int nw = w;
while (nw >= 0 && dp[0][nw] >= kInf)
--nw;
if (l == 1 && r == 200)
fout << nw << " " << dp[0][nw] << "\n";
nw = up[0][nw];
Solve(l, m, nw);
Solve(m + 1, r, w - nw);
}
int main() {
fin >> N >> G;
while (N--) {
int x;
fin >> x;
++a[x];
}
Solve(1, 200, G);
return 0;
}