Pagini recente » Cod sursa (job #2445476) | Cod sursa (job #1515019) | Cod sursa (job #3170591) | Cod sursa (job #1929680) | Cod sursa (job #271425)
Cod sursa(job #271425)
#include<fstream.h>
ifstream f("lupu.in");
ofstream g("lupu.out");
#define nmax 101000
struct vect
{
long inf,pct;
}h[nmax],h2[nmax];
long n,m,x,l,y,z,s,n2;
void urca(int k)
{
if(k>1&&h[k].inf>h[k/2].inf)
{
vect z=h[k];
h[k]=h[k/2];
h[k/2]=z;
urca(k/2);
}
}
void coboara(int k,int n)
{
long fiu=k;
if(2*k<=n)
{
if(h[fiu].inf<h[2*k].inf)
fiu=2*k;
if(h[fiu].inf<h[2*k+1].inf&&2*k+1<=n)
fiu=2*k+1;
if(fiu!=k)
{
vect z=h[fiu];
h[fiu]=h[k];
h[k]=z;
coboara(fiu,n);
}
}
}
void refacere(int n)
{
if(n>0)
{
vect z=h[1];
h[1]=h[n];
h[n]=z; n--;
coboara(1,n);
refacere(n);
}
}
void citire()
{
f>>m>>x>>l; n=m;
for(long i=1;i<=m;i++)
{
f>>y>>z;
y=(x-y)/l;
h[i].inf=y;
h[i].pct=z;
urca(i);
}
}
void coboara2(int k,int n)
{
long fiu=k;
if(2*k<=n)
{
if(h2[fiu].pct<h2[2*k].pct)
fiu=2*k;
if(h2[fiu].pct<h2[2*k+1].pct&&2*k+1<=n)
fiu=2*k+1;
if(fiu!=k)
{
vect z=h2[fiu];
h2[fiu]=h2[k];
h2[k]=z;
coboara(fiu,n);
}
}
}
void urca2(int k)
{
if(k>1&&h2[k].pct>h2[k/2].pct)
{
vect z=h2[k];
h[k]=h2[k/2];
h2[k/2]=z;
urca(k/2);
}
}
void program()
{
long v=h[m].inf;
long i=m;
while(v>=0&&i>0)
{
v=h[i].inf;
while(v==h[i].inf&&i>0)
{
h2[++n2]=h[i];
urca2(n2);
i--;
}
long j=v-h[i].inf;
while(j>0&&n2>0)
{
s+=h2[1].pct;
h2[1]=h2[n2];
n2--;
coboara2(1,n2);
j--;
}
}
}
void afisare()
{
g<<s<<'\n';
}
int main()
{
citire();
refacere(n);
program();
afisare();
f.close();
g.close();
return 0;
}