Cod sursa(job #589794)

Utilizator Smaug-Andrei C. Smaug- Data 13 mai 2011 20:06:03
Problema Lupul Urias si Rau Scor 32
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <queue>
using namespace std;

#define MAXN 100000

typedef struct Sheep {
  int t, w;
} Sheep;

struct hcmp {
  int operator()(const Sheep &a, const Sheep &b)const{
    return (a.w < b.w);
  }
};

int cmp(const void *a, const void *b){
  return (((Sheep*)b)->t - ((Sheep*)a)->t);
}

int main(){

  freopen("lupu.in", "r", stdin);
  freopen("lupu.out", "w", stdout);

  int N, X, L, i, a, b, s;
  Sheep F[MAXN+10];

  priority_queue< Sheep, vector<Sheep>, hcmp > Q;
  
  scanf("%d%d%d", &N, &X, &L);
  for(i=0; i<N; i++){
    scanf("%d%d", &a, &b);
    if(a <= X)
      F[i].t=((X-a)/L)+1;
    else
      F[i].t=0;
    F[i].w=b;
  }

  qsort(F, N, sizeof(Sheep), cmp);

  i=0; s=0;
  while(i<N && F[i].t){
    a=F[i].t;
    while(F[i].t == a){
      Q.push(F[i]);
      i++;
    }

    s+=Q.top().w;
    Q.pop();
    
  }

  printf("%d\n", s);

  return 0;

}