Cod sursa(job #2809508)

Utilizator Remus.RughinisRemus Rughinis Remus.Rughinis Data 27 noiembrie 2021 10:01:37
Problema Lupul Urias si Rau Scor 0
Compilator c-64 Status done
Runda Arhiva de probleme Marime 2.16 kb
#include <stdio.h>
#include <stdlib.h>
#define LMAX 100000

int heap[LMAX],hs,v[LMAX],ln[LMAX];

static inline int parent(int i) {return (i - 1) / 2;}
static inline int leftChild(int i) {return i * 2 + 1;}
static inline int rightChild(int i) {return i * 2 + 2;}

void quicksort(int begin, int end){
  int b = begin, e = end, pivot = v[(begin + end)/2], aux;

  while(v[b] > pivot)
    b++;
  while(v[e] < pivot)
    e--;

  while(b<e){
    aux = v[b];
    v[b] = v[e];
    v[e] = aux;

    aux = ln[b];
    ln[b] = ln[e];
    ln[e] = aux;

    do{
      b++;
    } while(v[b] > pivot);
    do{
      e--;
    } while(v[e] < pivot);
  }

  if(e > begin)
    quicksort(begin, e);
  if(e+1 < end)
    quicksort(e+1, end);
}

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

void climbHeap(int x){
  if(x == 0)
    return;

  int p = parent(x);

  if( heap[p] < heap[x] )
    swap(x, p);
}

void downHeap(int x){
  if(x >= hs)
    return;

  int st = leftChild(x), dr = leftChild(x), aux;

  if(heap[st] == 0)
    return;
  if(heap[dr] != 0 && heap[dr] > heap[st]){
    swap(dr,st);

    aux = dr;
    dr = st;
    st = aux;
  }

  if(heap[st] > heap[x]){
    swap(x, st);
    downHeap(st);
  }

}

void deleteMin(){
  heap[0] = heap[hs-1];
  hs--;

  downHeap(0);
}

void add(int x){
  heap[hs] = x;
  hs++;

  climbHeap(hs-1);
}

int main(){
  int n,x,l,s,i,d;
  FILE *fin, *fout;

  fin = fopen("lupu.in","r");
  fscanf(fin,"%d%d%d",&n,&x,&l);

  for(i=0;i<n;i++){
    fscanf(fin,"%d%d",&d,&ln[i]);

    if(x >= d)
      v[i] = (x-d) / l +1;
//    printf("%d ",v[i]);
  }
  quicksort(0,n-1);

//  for(i=0;i<n;i++)
//    printf("%d ",v[i]);
//  printf("\n");
//  for(i=0;i<n;i++)
//    printf("%d ",ln[i]);
//  printf("\n");

  i = 0;
  s = 0;
//  printf("\n",heap[0]);
  while(i<n){
    x = v[i];
    while(i<n && v[i] == x){
      add(ln[i]);
      i++;
    }

    s+= heap[0];
//    printf("%d ",heap[0]);
    deleteMin();
  }

  fclose(fin);

  fout = fopen("lupu.out","w");
  fprintf(fout,"%d\n",s);
  fclose(fout);
  return 0;
}