Cod sursa(job #69590)

Utilizator anna_bozianuBozianu Ana anna_bozianu Data 3 iulie 2007 16:26:01
Problema Lupul Urias si Rau Scor 32
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.37 kb
#include<stdio.h>
int swap(long long int i1,long long int i2);
int heapdown(long long int ic,long long int nc);
int qs(long long int ll,long long rr);
long long int n,dm,p,a[100001],d[100001],i,aux,sol,maxday,dc,poz,p1;
int main()
{
	FILE *f,*g;
	f=fopen("lupu.in","r");
	g=fopen("lupu.out","w");
	fscanf(f,"%lld%lld%lld",&n,&dm,&p);
	maxday=dm/p+1;
	for(i=1;i<=n;i++)
	{ fscanf(f,"%lld%lld",&d[i],&a[i]);
	  if(d[i]<=dm) d[i]=(dm-d[i])/p+1;
	  else {n--;i--;}
	}
	for(i=n/2;i>=1;i--)
	heapdown(i,n);
	for(i=n;i>=1;i--)
	{ swap(1,i);heapdown(1,i-1);}
	dc=maxday;
	poz=n;
	p1=n;
	while(dc)
	{ while(d[p1]>=dc)p1--;
	  qs(p1+1,poz);
	  sol+=a[poz];
	  dc--;poz--;
	}
	fprintf(g,"%lld\n",sol);
	fcloseall();
	return 0;
}
int swap(long long int i1,long long int i2)
{
	aux=d[i1];d[i1]=d[i2];d[i2]=aux;
	aux=a[i1];a[i1]=a[i2];a[i2]=aux;
	return 0;
}
int heapdown(long long int ic,long long int nc)
{
	long long int is=2*ic,is1=2*ic+1;
	if(is>nc) return 0;
	if(is<nc)
	 if(d[is]<d[is1])is=is1;
	if(d[ic]<d[is])
	{ swap(ic,is);heapdown(is,nc);}
	return 0;
}
int qs(long long int ll,long long rr)
{
	long long int lll,rrr,vm;
	lll=ll;rrr=rr;
	vm=a[(ll+rr)/2];
	do
	{
		while(a[lll]<vm)lll++;
		while(a[rrr]>vm)rrr--;
		if(lll<=rrr) { swap(lll,rrr);lll++;rrr--;}
	}
	while(lll<=rrr);
	if(ll<rrr) qs(ll,rrr);
	if(lll<rr) qs(lll,rr);
	return 0;
}