Cod sursa(job #277770)

Utilizator stocarulCosmin-Mihai Tutunaru stocarul Data 11 martie 2009 21:42:54
Problema Lupul Urias si Rau Scor 20
Compilator c Status done
Runda Arhiva de probleme Marime 3.26 kb
#include<stdio.h>
#define infile "lupu.in"
#define outfile "lupu.out"
#define nmax 100*1001
struct oaie
	{
	int m; //numarul maxim de mutari dupa care lupul poate sa i-a aceasta oaie
	int l; //lana adusa de aceasta oaie
	} o[nmax]; //oile :>
int h[nmax],nrh; //max-heap-ul
int n; //numarul de oi
int x; //distanta maxima de la care lupul poate alege
int l; //distanta cu care se deplaseaza fiecare oaie dupa ce lupul alege o oaie

void comb_sus_heap(int x)
	{ //urcam pozitia x in sus, pana o plaam corect
	int f=x,t=x/2; //fiul si tatal
	x=h[x]; //elementul ce trebuie plasat corecte
	while(t&&o[h[t]].l<o[x].l) //cat timp tatal e mai mic
		{
		h[f]=h[t]; //schimbam tatal cu fiul
		f=t; t=f/2; //refacem tatal si fiul
		}
	h[f]=x; //plasam corect
	}

void comb_jos_heap(int x)
	{ //coboram pe x in jos, pana il plasam corect
	int t=x,f=2*x; //tatal si fiul
	x=h[x]; //elementul ce trebuie plasat corect
	while(f<=nrh)
		{
		if(f<nrh&&o[h[f]].l<o[h[f+1]].l) f++; //e mai mare al doilea fiu
		if(o[h[f]].l>o[x].l) //fiul este mai mare
			{
			h[t]=h[f]; //schimbam tatal cu fiul
			t<<=1; f<<=1; //refacem tatal si fiul
			}
		else break; //i-am gasit pozitia...oprim cautarea
		}
	h[t]=x; //plasam corect in heap
	}

void add_heap(int x)
	{ //adauga oaia x in heap
	h[++nrh]=x; //adaugam oaia pe ultima pozitie
	comb_sus_heap(nrh); //o plasam la pozitia corecta
	}

int extrag_heap()
	{
	if(!nrh) return 0; //heap-ul este gol
	int v=h[1]; //varful heap-ului
	h[1]=h[nrh--]; //punem ultimul element din heap, in varful heap-ului
	comb_jos_heap(1); //acum il plasam corect
	return v; //returnam valoarea
	}

void citire()
	{
	int i;
	scanf("%d %d %d\n",&n,&x,&l);
	for(i=1;i<=n;i++)
		scanf("%d %d\n",&o[i].m,&o[i].l); //distanta fata de lup, si cantitatea de lana a oii i
	}

void preprocesare()
	{
	//transformam la fiecare oaie distanta fata de lup, in numarul maxim al mutarii in care lupul poate alege oaia
	int i;
	for(i=1;i<=n;i++)
		if(o[i].m>x) o[i].m=-1; //este deja la o distanta prea mare
		else if(!l) o[i].m=i; //oile nu se muta, deci toate oile pot fi luate
		else o[i].m=(x-o[i].m)/l;
	}

int divide(int p, int q)
	{
	struct oaie x=o[p]; //oaia ce trebuie plasata corect
	while(p<q)
		{
		while(p<q && o[q].m<=x.m) q--; //cat timp oaia din dreapta e mai mica
		o[p]=o[q];
		while(p<q && o[p].m>=x.m) p++; //cat timp oaia din partea stanga e mai mare
		o[q]=o[p];
		}
	o[p]=x; //plasam oaia corect
	return p; //returnam pozitia unde a fost plasata
	}

//sorteza intervalul [p,q] descrescator dupa m
void qsort(int p, int q)
	{
	int m=divide(p,q); //plasam corect pe p
	if(p<m-1) qsort(p,m-1); //sortam partea stanga
	if(m+1<q) qsort(m+1,q); //sortam partea dreapta
	}

long long numara()
	{
	long long nr=0; //initial cantitatea e 0
	int i,j;
	for(i=o[j=1].m;i>=0;i--) //fiecare mutare posibila
		{
		while(o[j].m==i&&j<=n) add_heap(j++); //adaugam toate oile care trebuie sa intre in timpul asta
		nr+=o[extrag_heap()].l; //extragem maximul
		}
	return nr;
	}

int main()
{
freopen(infile,"r",stdin);
freopen(outfile,"w",stdout);

citire();
preprocesare();
qsort(1,n); //sortam oile
printf("%lld",numara()); //numaram si afisem cantitatea maxima de lana

fclose(stdin);
fclose(stdout);
return 0;
}