Cod sursa(job #1867028)

Utilizator hrazvanHarsan Razvan hrazvan Data 3 februarie 2017 17:52:55
Problema Peste Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
#include <cstdio>
#include <algorithm>
#define MAXN 50000
#define MAXK 50000
typedef struct{
  int p, t;
}pr;
pr v[MAXN];
int heap[MAXK], dh = 0;

bool cmp(pr a, pr b){
  if(a.t < b.t)
    return 1;
  return 0;
}

inline void intersch(int x, int y){
  int aux;
  aux = heap[x];
  heap[x] = heap[y];
  heap[y] = aux;
}

inline void urc(int x){
  while(x > 0 && heap[(x - 1) / 2] > heap[x]){
     intersch((x - 1) / 2, x);
     x = (x - 1) / 2;
  }
}

inline void cobor(int x){
  int best = x;
  do{
    x = best;
    if(heap[best] > heap[2 * x + 1])
      best = 2 * x + 1;
    if(2 * x + 2 < dh && heap[best] > heap[2 * x + 2])
      best = 2 * x + 2;
    intersch(x, best);
  }while(2 * best + 1 < dh && best != x);
}

int main(){
  FILE *in = fopen("peste.in", "r");
  int k, n, t, i, sum = 0, rez = 0;
  fscanf(in, "%d%d%d", &k, &n, &t);
  for(i = 0; i < n; i++)
    fscanf(in, "%d%d", &v[i].p, &v[i].t);
  fclose(in);
  std::sort(v, v + n, cmp);
  for(i = 0; i < n; i++){
    if(dh < k){
      sum += v[i].p;
      heap[dh] = v[i].p;
      urc(dh);
      dh++;
    }
    else{
      if(heap[0] < v[i].p){
        sum -= heap[0];
        heap[0] = v[i].p;
        cobor(0);
      }
    }
    if(t / v[i].t * sum > rez)
      rez = t / v[i].t * sum;
  }
  FILE *out = fopen("peste.out", "w");
  fprintf(out, "%d", rez);
  fclose(out);
  return 0;
}