Cod sursa(job #334426)

Utilizator Anamaria20Cotirlea Anamaria Anamaria20 Data 26 iulie 2009 18:35:39
Problema Lupul Urias si Rau Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.78 kb
#include <stdio.h>
#include <algorithm>

using namespace std;

FILE *f,*s;

int n,k,l,i,j,tmax,h[100005],N;

long long int rez;

struct oaie
{
	int x;
	int y;
	int t;
};	

oaie v[100005];

int cmp(oaie a, oaie b)
{
	return a.t>b.t;
}	

int father(int nod)
{  
	return nod/2;  
}  
  
int left_son(int nod)
{  
	return nod*2;  
}  
   
int right_son(int nod)
{  
	return nod*2+1;  
}

int max(int h[100005])
{  
	return h[1];  
}  

void percolate(int N, int K) 
{  
	int key=h[K];  
      
	while((K>1)&&(key>h[father(K)])) 
	{  
		h[K]=h[father(K)];  
		K=father(K);  
	}  
      
	h[K]=key;  
}

void sift(int N, int K) 
{  
	int son;
	
	do 
	{  
		son=0;  
              
		if(left_son(K)<=N)
		{  
			son=left_son(K);
			
			if(right_son(K)<=N&&h[right_son(K)]>h[left_son(K)])
			{  
				son=right_son(K);  
			}  
			
			if(h[son]<=h[K])
			{  
				son=0;  
			}  
		}  
    
		if(son)
		{  
			swap(h[K],h[son]);   
			K=son;  
		}
		
	} while (son);  
}  

void insert(int h[100005], int &N, int key)
{  
	h[++N]=key;  
	percolate(N, N);  
}  


void cut(int h[100005], int &N, int K)
{  
	h[K]=h[N];  
	--N;  
      
	if ((K>1)&&(h[K]>h[father(K)]))
	{  
		percolate(N, K);  
	} 
	else 
	{  
		sift(N, K);  
	}  
}  

int main()
{
	f=fopen("lupu.in","r");
	s=fopen("lupu.out","w");
	
	fscanf(f,"%d %d %d\n",&n,&k,&l);
	
	for(i=1;i<=n;i++)
	{
		fscanf(f,"%d %d\n",&v[i].x,&v[i].y);
		
		v[i].t=(k-v[i].x)/l+1;
		
		if(v[i].t>tmax)
			tmax=v[i].t;
	}
	
	sort(v+1,v+n+1,cmp);
	
	j=1;
	for(i=tmax;i>0;i--)
	{
		while(v[j].t==i&&j<=n)
		{
			//insert(h,N,v[j].y);
			j++;
		}	
		
		rez+=max(h);
		
		cut(h,N,1);
	}	
	
	fprintf(s,"%lld\n",rez);
	
	fclose(s);
	
	return 0;
}