Pagini recente » Cod sursa (job #1037970) | Cod sursa (job #2323316) | Cod sursa (job #717653) | Cod sursa (job #1362015) | Cod sursa (job #277397)
Cod sursa(job #277397)
#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(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+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&&o[i].m!=-1;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;
}