Cod sursa(job #371114)

Utilizator nicolaetitus12Nicolae Titus nicolaetitus12 Data 3 decembrie 2009 20:55:36
Problema Lupul Urias si Rau Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <stdio.h>
#define M 132000
#define N 100001
int d[N],a[N],next[N],p[N];
int dawg[N];
int heap[M];
int sir1[N],sir2[N];
/*
void down()
{

}

void up()
{

}

int top()
{

}

int pop()
{

}

void
{

}
*/

int main ()
{
 freopen("lupu.in","r",stdin);
 freopen("lupu.out","w",stdout);
 int k,n,x,l,i,j,idx,vf=0,max;
 int *p1=sir1,*p2=sir2,*aux;
 scanf("%d %d %d",&n,&x,&l);
 k=(x+1)%l;
 for (i=1;i<=n;i++)
 {scanf("%d %d",&d[i],&a[i]);
  idx=(d[i]+l-k)/l;
  if(vf<idx)vf=idx;
  next[i]=p[idx];
  p[idx]=i;
 }

 //init primul segment
 for (j=p[vf];j;j=next[j])
 {if(max<d[j])max=d[j];}
 p1[1]=max;;
 for (i=vf-1;i>=0;i--)
 {if(p[i])
  {vh=0;
   for (j=p[i];j;j=next[j])
   {heap[++vh]=d[j];
    up(vh);
   }
   if(vh>1)
   {sum=pop();
    max=0;
    for (k=vf-i;k>=1;k--)
    {for (j=k;vh>0&&j>=1;j--)
     {if(max<sum+p1[j])
      {max=sum+p1[j];
      }
      sum+=pop();
     }
     if(max<sum)
     {max=sum;
     }
    }
   }
  }
 }
 
 
 return 0;
}