Cod sursa(job #1290819)

Utilizator vladrochianVlad Rochian vladrochian Data 11 decembrie 2014 19:53:18
Problema Ghiozdan Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 1.41 kb
#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;
}