Pagini recente » Cod sursa (job #1433076) | Cod sursa (job #2968229) | Cod sursa (job #2746974) | Cod sursa (job #1513271) | Cod sursa (job #277792)
Cod sursa(job #277792)
#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>>=1; t>>=1; //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=f; 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
{
//if(!nrh) i=o[j].m; //daca heap-ul e gol...ne ducem direct la prima oita nerezolvata
//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;
}