Cod sursa(job #1318510)

Utilizator YusukeFMI Mares Medar Razvan Yusuke Data 16 ianuarie 2015 00:14:06
Problema Lupul Urias si Rau Scor 12
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.89 kb
#include <iostream>
#include <stdio.h>
#include <algorithm>
#define nmax 100001
using namespace std;
struct oi  {int d,a,t;}   oaie[nmax],z;
int n,nroi,x,l,S,h[nmax],i,j;
void urca(int nod)
      {int aux;
       while(nod/2 && h[nod/2]<h[nod])
                   {aux=h[nod/2];h[nod/2]=h[nod];h[nod]=aux;nod/=2;}
      }
void coboara(int nod)
     {int nodfiu,aux;
      nodfiu=nod*2;
      while(nodfiu!=nod)
              {nodfiu=nod;
               if(nod*2<=h[0] && h[nodfiu]<h[nod*2])      nodfiu=nod*2;
               if(nod*2+1<=h[0] && h[nodfiu]<h[nod*2+1])  nodfiu=nodfiu*2+1;
               aux=h[nodfiu];h[nodfiu]=h[nod];h[nod]=aux;
               nod=nodfiu;
               }
      }
void citire()
     {freopen("lupu.in","r",stdin);
      scanf("%d %d %d",&n,&x,&l);
      for(i=1;i<=n;i++)   {scanf("%d %d",&z.d,&z.a);
                           if(z.d<=x)     oaie[++nroi]=z;
                           }
      fclose(stdin);
      }
void scrie()
     {freopen("lupu.out","w",stdout);
      printf("%d",S);
      fclose(stdout);
      }
bool cmp(oi u1,oi u2)
     {return u1.t<u2.t;}
int main()
    {citire();
     if(!l)     {for(i=1;i<=nroi;i++)
                           S+=oaie[i].a;
               }
     else      {for(i=1;i<=nroi;i++)       oaie[i].t=1+(x-oaie[i].d)/l;
                sort(oaie+1,oaie+1+nroi,cmp);
                j=nroi;
                for(i=oaie[nroi].t;i>=1;i--)
                           {for(;j>=1;j--)
                                     {if(i==oaie[j].t)
                                                  {h[++h[0]]=oaie[j].a;urca(h[0]);}
                                      else
                                                   break;
                                      }
                            S+=h[1];h[1]=h[h[0]--];coboara(1);
                            }
                }
     scrie();
     return 0;
     }