Cod sursa(job #80900)

Utilizator ada_sAda-Mihaela Solcan ada_s Data 30 august 2007 15:08:36
Problema Lupul Urias si Rau Scor 76
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.55 kb
#include <fstream>
std::ifstream f1("lupu.in");
std::ofstream f2("lupu.out");

struct elem { long d,a;};

long part(struct elem sir[110000], long jos, long sus);
void quicksort(struct elem sir[110000], long jos, long sus);


int main()
{
	struct elem sir[110000];
	long n, x, l, poz, dmax, i, dtemp, atemp;
	int liber[110000];
	long long sol;
	f1>>n>>x>>l;
	poz=0;
	dmax=-1;
	for (i=0; i<n; i++)
	{
		f1>>dtemp>>atemp;
		if (dtemp<=x)
		{
			sir[poz].d=(x-dtemp)/l;
			sir[poz].a=atemp;
			if (sir[poz].d>dmax)
				dmax=sir[poz].d;
			poz++;
		}//if
	}//for i
	n=poz;
	quicksort(sir, 0, n-1);
//	for (i=0; i<n; i++)/////////////////////////
//		f2<<sir[i].d<<" "<<sir[i].a<<"\n";////////////////////
	for (i=0; i<n; i++)
		liber[i]=1;
	sol=0;
	for (i=0; i<n; i++)
	{
		poz=sir[i].d;
		if (liber[poz]<2)
		{
  		while ((liber[poz]!=1)&&(poz>=0))
	  		poz--;
		  if (poz>=0)
  		{
	  		sol+=sir[i].a;
		  	liber[poz]=0;
  		}//if
	  	else
		  	liber[sir[i].d]=2;
		}//if
  }//for i
	f2<<sol;
	f1.close();
	f2.close();
	return 0;
}//main

long part(struct elem sir[110000], long jos, long sus)
{
	long p, q;
	struct elem temp;
	p=jos;
	q=sus;
	while (p<q)
	{
		while ((sir[p].a>=sir[jos].a)&&(p<=q))
			p++;
		while ((sir[q].a<sir[jos].a)&&(q>=p))
			q--;
		if (p<q)
		{
			temp=sir[p];
			sir[p]=sir[q];
			sir[q]=temp;
		}//if
	}//while
	temp=sir[q];
	sir[q]=sir[jos];
	sir[jos]=temp;
	return q;
}//part

void quicksort(struct elem sir[110000], long jos, long sus)
{
	if (jos<sus)
	{
		long p=part(sir, jos, sus);
		quicksort(sir, jos, p-1);
		quicksort(sir, p+1, sus);
	}//if
}//quicksort