Cod sursa(job #589800)

Utilizator Smaug-Andrei C. Smaug- Data 13 mai 2011 20:26:09
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 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, t;
  long long 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; 
  for(t=F[i].t; t>0 && i<N; t--){
    while(F[i].t == t){
      Q.push(F[i]);
      i++;
    }
    if(!Q.empty()){
      s+=Q.top().w;
      Q.pop();
    }
    
  }

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

  return 0;

}