Cod sursa(job #69624)

Utilizator anna_bozianuBozianu Ana anna_bozianu Data 3 iulie 2007 17:51:53
Problema Lupul Urias si Rau Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.67 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 heapup(long long int ic);
int heapdown1(long long int ic,long long int nc);
long long int n,dm,p,a[1001],d[1001],heap[1001],i,aux,sol,maxday,dc,poz,p1,lheap;
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;
	for(dc=maxday;dc>=1;dc--)
	{ while(d[poz]==dc)
	  { lheap++;heap[lheap]=a[poz];heapup(lheap);poz--;}
	  if(lheap)
	  { sol+=heap[1];heap[1]=heap[lheap];lheap--;
	    heapdown1(1,lheap);
	  }
	}
	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 heapup(long long int ic)
{
	long long int pc=ic/2;
	if(pc)
	 if(heap[ic]>heap[pc])
	  { aux=heap[ic];heap[ic]=heap[pc];heap[pc]=aux;
	    heapup(pc);
	  }
	return 0;
}
int heapdown1(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(heap[is]<heap[is1])is=is1;
	if(heap[ic]<heap[is])
	{ aux=heap[ic];heap[ic]=heap[is];heap[is]=aux;heapdown1(is,nc);}
	return 0;
}