Pagini recente » Cod sursa (job #162128) | Cod sursa (job #2310029) | Cod sursa (job #2861142) | Cod sursa (job #2572368) | Cod sursa (job #2058128)
#include <bits/stdc++.h>
using namespace std;
const int MAXG = 75e3;
const int MAXOBJ = 200;
const int INF = 0x3f3f3f3f;
deque <pair <int, int>> deq;
int freq[MAXOBJ + 1];
ofstream fout("ghiozdan.out");
void solve(int l, int r, int gr) {
if (gr == 0)
return;
if (l == r) {
for (int i = 0; i < freq[l] && i * l < gr; ++i)
fout << l << '\n';
return;
}
int mid = (l + r) / 2;
vector <int> dp[2], prv[2];
for (int i = 0; i < 2; ++i) {
prv[i].resize(gr + 1);
dp[i].resize(gr + 1);
}
fill(dp[0].begin(), dp[0].end(), INF);
dp[0][0] = 0;
for (int i = l; i <= r; ++i)
if (freq[i]) {
for (int rest = 0; rest < i; ++rest) {
deq.clear();
for (int j = rest; j <= gr; j += i) {
int cost = dp[0][j] + j / i;
while (deq.empty() == false && deq.front().first < j - i * freq[i])
deq.pop_front();
while (deq.empty() == false && deq.back().second >= cost)
deq.pop_back();
deq.push_back({j, cost});
cost = deq.front().first;
dp[1][j] = dp[0][cost] + (j - cost) / i;
prv[1][j] = (i > mid) ? prv[0][cost] : j;
}
}
dp[0] = dp[1];
prv[0] = prv[1];
}
int lstgr = gr;
while (lstgr >= 0 && dp[0][lstgr] >= INF)
--lstgr;
if (l == 1 && r == MAXOBJ)
fout << lstgr << " " << dp[0][lstgr] << '\n';
solve(l, mid, prv[0][lstgr]);
solve(mid + 1, r, gr - prv[0][lstgr]);
}
int main()
{
int n, g;
ifstream fin("ghiozdan.in");
fin >> n >> g;
for (int i = 0; i < n; ++i) {
int num;
fin >> num;
++freq[num];
}
fin.close();
solve(1, 200, g);
fout.close();
return 0;
}