Cod sursa(job #271642)

Utilizator ConsstantinTabacu Raul Consstantin Data 5 martie 2009 18:51:44
Problema Lupul Urias si Rau Scor 56
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 kb
#include<stdio.h>
#include<algorithm>
using namespace std;

struct oi{int d,c;}v[100011];
unsigned int i,x,j,k,l,m,n,h[100011];
unsigned long long int sol;

void add(int poz,unsigned int val)
        {unsigned int aux;
        h[poz]=val;
        while(h[poz]>h[poz/2]&&poz>1)
                {aux=h[poz];
                h[poz]=h[poz/2];
                h[poz/2]=aux;
                poz=poz/2;}
       }
int cmp(oi a,oi b){
return a.d<b.d;}


void del(int poz)
{int p,u,aux;
h[poz]=0;
while(poz<i)
        {p=poz*2;
        u=p+1;
        if(!h[p]&&(!h[u]))return ;
        if(h[p]>h[u]){
                 aux=h[poz];
                 h[poz]=h[p];
                 h[p]=aux;
                 poz=p;
                 }
      else
      {aux=h[poz];
      h[poz]=h[u];
      h[u]=aux;
      poz=u;
      }
     }
}
int main(){

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

scanf("%d %d %d",&n,&x,&l);

for(i=1;i<=n;i++)
        scanf("%d %d",&v[i].d,&v[i].c);

sort(v+1,v+1+n,cmp);

m=x%l;
for(i=1;v[i].d<=m;i++)
        add(i,v[i].c);
sol+=h[1];
del(1);
m+=l;

for(m;m<=x;m+=l)
        {for(i=i;v[i].d<=m&&i<=n;i++)
                add(i,v[i].c);
        sol+=h[1];
        del(1);
        }
printf("%d",sol);
return 0;}