Pagini recente » Rating Chiriac Casian (Casian_doispe) | Cod sursa (job #2519186) | Cod sursa (job #2590661) | Cod sursa (job #2218305) | Cod sursa (job #423266)
Cod sursa(job #423266)
#include<stdio.h>
int q[100001],g[100001],prec[100001];
char o[100001];
void swap(int *x,int *y)
{
int temp;
temp = *x;
*x = *y;
*y = temp;
}
void quicksort(int m,int n)
{
int key,i,j,k,t;
if( m < n)
{
k = (m+n)/2;
swap(&g[m],&g[k]);
key = g[m];
i = m+1;
j = n;
while(i <= j)
{
while((i <= n) && (g[i] <= key))
i++;
while((j >= m) && (g[j] > key))
j--;
if( i < j)
{
t=g[i];
g[i]=g[j];
g[j]=t;
t=q[i];
q[i]=q[j];
q[j]=t;
}
}
t=g[m];
g[m]=g[j];
g[j]=t;
t=q[m];
q[m]=q[j];
q[j]=t;
quicksort(m,j-1);
quicksort(j+1,n);
}
}
int main()
{
int n,h,u,i,start,max=0,val,stac[100000],j,k;
freopen("gutui.in","r",stdin);
freopen("gutui.out","w",stdout);
scanf("%d %d %d",&n,&h,&u);
for(i=1;i<=n;i++)
scanf("%d %d",&(q[i]),&(g[i]));
quicksort(1,n);
for(i=n;i>0;--i) {
start=1+(h-q[i])/u;
k=1;
stac[k]=start;
while(prec[start] && start>0)
{
start=prec[start];
stac[++k]=start;
}
if(start>0)
{
if(start!=1)
if(prec[start-1])
val=prec[start-1];
else
val=start-1;
else
val=-1;
for(j=1;j<=k;j++)
prec[stac[j]]=val;
max+=g[i];
o[start]=1;
}
}
printf("%d\n",max);
return 0;
}