Cod sursa(job #2253684)

Utilizator stefan_creastaStefan Creasta stefan_creasta Data 4 octombrie 2018 11:45:15
Problema Minim2 Scor 40
Compilator cpp Status done
Runda shimulare_fara_shim Marime 1.48 kb
#include <cstdio>
#include <queue>
using namespace std;
const int NMAX = 100005;
const int PUTMAX = 2000;
double v[NMAX];
double put[PUTMAX + 5];
struct Drum {
  double val;
  double im;
  bool operator < (const Drum &other) const {
    return (this->val - this->val * this->im) < (other.val - other.val * other.im);
  }
};
double sum, k;
priority_queue <Drum> pq;
/*int cb(double val1, double val2) {
  int st = 0, dr = PUTMAX;
  int last = 0;
  while(st <= dr) {
    int mij =(st + dr) / 2;
    double val = val1 * put[mij];
    sum = sum - val1 + val;
    if(val < val2 || sum < k) {
      last = mij;
      dr = mij - 1;
    }
    else {
      st = mij + 1;
    }
    sum = sum + val1 - val;
  }
  return last;
}*/

int main() {
  int n;
  freopen("minim2.in", "r", stdin);
  freopen("minim2.out", "w", stdout);
  scanf("%d", &n);
  for(int i = 1; i <= n; i++) {
    scanf("%lf", &v[i]);
    sum += v[i];
  }
  double a, b;
  scanf("%lf%lf%lf", &a, &b, &k);
  for(int i = 1; i <= n; i++) {
    pq.push({v[i], a});
  }
  /*put[0] = 1;
  for(int i = 1; i <= PUTMAX; i++) {
    put[i] = put[i - 1] * b;
  }*/
  long long sol = 0;
  while(sum >= k) {
    Drum nr2, nr1 = pq.top();
    pq.pop();
    if(!pq.empty()) {
      nr2 = pq.top();
    }
    else {
      nr2.val = k;
    }
    sum -= nr1.val;
    if(nr1.im == a) {
      nr1.val *= a;
      nr1.im = b;
      sol++;
    }
    else {
      nr1.val *= b;
      sol++;
    }
    sum += nr1.val;
    pq.push(nr1);
  }
  printf("%lld\n", sol);
  return 0;
}