Cod sursa(job #14542)

Utilizator vlad_popaVlad Popa vlad_popa Data 9 februarie 2007 12:05:09
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.82 kb
using namespace std;

#include <cstdio>
#include <algorithm>
#include <queue>

#define FIN "lupu.in"
#define FOUT "lupu.out"
#define NMAX 100001

int v[NMAX], N, X, L, tmax, dimheap;
struct lupi {int a, t;};
lupi l[NMAX];
int ord[NMAX];

int cmp (const int a, const int b)
{
  return l[a].t > l[b].t;
}

void reconst_heap (int i)
{
  int l, r, maxim;
  l = (i<<1);
  r = (i<<1) + 1;
  if (l <= dimheap && v[l] > v[i])
    maxim = l;
   else
    maxim = i;
  if (r <= dimheap && v[r] > v[maxim])
    maxim = r;
  if (maxim != i)
   {
     v[i] ^= v[maxim];
     v[maxim] ^= v[i];
     v[i] ^= v[maxim];
     reconst_heap (maxim);
   }
}

int extr_max_heap ()
{
  int max;
  if (dimheap < 1)
   return 0;
  dimheap--;
  max = v[1];
  v[1] = v[dimheap + 1];
  reconst_heap(1);
  return max;
}

void insert_heap (int cheie)
{
  int i;
  dimheap++;
  i = dimheap;
  while (i > 1 && v[(i>>1)] < cheie)
   { v[i] = v[(i>>1)];
     i >>= 1;
   }
  v[i] = cheie;
}

int
 main ()
{
  int i, P = 0, k, j;
  long long s = 0;
  freopen (FIN, "rt", stdin);
  freopen (FOUT, "wt", stdout);
  scanf ("%d%d%d", &N, &X, &L);
  scanf ("%d%d", &l[1].t, &l[1].a);
  ord[1] = 1;
  l[1].t = (X - l[1].t) / L;
  if (tmax < l[1].t)
    tmax = l[1].t;
  for (i = 2; i <= N; i++)
   {
     scanf ("%d%d", &l[i].t, &l[i].a);
     ord[i] = i;
     l[i].t = (X - l[i].t) / L;
     if (l[i].t > l[i-1].t) P = 1;
     if (tmax < l[i].t)
      tmax = l[i].t;
   }
  k = 1;
  l[N+1].t = 100;
  ord[N+1] = N+1;
  if (P == 1)
    sort (ord+1, ord+N+1, cmp);
  for (j = tmax; j >= 0; j--)
   {
     if (l[ord[k]].t == j)
       while (l[ord[k]].t == j)
        {
          insert_heap (l[ord[k]].a);
          k++;
        }
     s += extr_max_heap ();
   }  
  printf ("%lld\n", s);
  return 0;
}