Cod sursa(job #277389)

Utilizator stocarulCosmin-Mihai Tutunaru stocarul Data 11 martie 2009 18:16:06
Problema Lupul Urias si Rau Scor 4
Compilator c Status done
Runda Arhiva de probleme Marime 2.06 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 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 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(!l) o[i].m=i; //oile nu se muta, deci trebuie sa avem numere diferite pe fiecare oaie (pt a le putea alege pe toate oile)
		else o[i].m=(x-o[i].m)/l+1;
	}

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 || (o[q].m==x.m && o[q].l<=x.l))) q--; //cat timp oaia din dreapta e mai mica
		o[p]=o[q];
		while(p<q && (o[p].m>x.m || (o[p].m==x.m && o[p].l>=x.l))) 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, respectiv l
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;
	for(i=1;i<=n;i++) //trecem pe la fiecare oaie
		{
		nr+=o[i].l; //adaugam lana oii
		while(o[i+1].m==o[i].m) i++; //cat timp este din aceeasi mutare
		}
	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;
}