Cod sursa(job #439534)

Utilizator 2fastGherghina Alexandru 2fast Data 11 aprilie 2010 16:53:00
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 1.33 kb
#include <fstream>
#include <iostream>
#include <stdlib.h>
using namespace std;

typedef struct nod
{
	unsigned int gr,nr;
	nod *next;
}nod;

ifstream f("gutui.in");
ofstream g("gutui.out");
int m;
unsigned int n,h,u,l,gr,nr;
unsigned int *heap;

int compare (const void * a, const void * b)
{
  return ( ((nod*)a)->nr - ((nod*)b)->nr );
}

void heapify(int k)
{
	int s,d;
	s=2*k;
	d=s+1;
	if(s<=m)
	{
		unsigned int temp;
		if(heap[k]>heap[s])
			if(heap[s]>heap[d] && d<=m)
			{
				temp=heap[d];
				heap[d]=heap[k];
				heap[k]=temp;
				heapify(d);
			}
			else
			{
				temp=heap[s];
				heap[s]=heap[k];
				heap[k]=temp;
				heapify(s);
			}
		else if(heap[k]>heap[d] && d<=m)
		{
			temp=heap[d];
			heap[d]=heap[k];
			heap[k]=temp;
			heapify(d);
		}
	}
}

int main()
{
	f>>n;
	f>>h>>u;
	heap=new unsigned int[n+1];
	int i,j;
	nod v[n+1];
	for(i=0;i<n;i++)
	{
		f>>l>>gr;
		v[i].gr=gr;
		v[i].nr=(h-l)/u+1;
	}
	qsort(v,n,sizeof(nod),compare);
	unsigned int ut=0;
	for(i=0;i<n;i++)
	{
		if(v[i].nr>ut)
		{
			heap[++m]=v[i].gr;
			ut++;
			for(j=m/2;j>0;j--)
				heapify(j);
		}
		else if(heap[1]<v[i].gr)
		{
			heap[1]=v[i].gr;
			heapify(1);
		}	
	}
	unsigned int max=0;
	for(i=1;i<=m;i++)
		max+=heap[i];
	g<<max<<endl;
	f.close();
	g.close();
	return 0;
}