Cod sursa(job #2058126)

Utilizator cella.florescuCella Florescu cella.florescu Data 5 noiembrie 2017 10:28:17
Problema Ghiozdan Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.73 kb
#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;
}