Pagini recente » Cod sursa (job #1512473) | Cod sursa (job #1881209) | Cod sursa (job #1925011) | Cod sursa (job #1333309) | Cod sursa (job #270349)
Cod sursa(job #270349)
#include<fstream.h>
ifstream f("lupu.in");
ofstream g("lupu.out");
#define nmax 101000
struct elem
{
long inf,pct;
elem *ant,*urm;
} *c,*p;
struct vect
{
long pt,nrv;
}a[nmax],d;
long n,x,l,y,z,w,n1,s,k;
void citire()
{
f>>n>>x>>l;
c=new elem;
f>>y>>z;
c->inf=-1;
c->pct=0;
c->ant=NULL;
c->urm=NULL;
p=c;
elem *q=new elem;
q->inf=(x-y)/l;
q->pct=z;
q->ant=c;
q->urm=NULL;
c->urm=q;
c=q;
q=new elem;
q->inf=n+1;
q->urm=NULL;
q->ant=c;
c->urm=q;
c=q;
for(long i=2;i<=n;i++)
{
f>>y>>z;
w=(x-y)/l;
if(w>=0)
{
if(c->inf>w)
{
while(c->inf>w)
c=c->ant;
while(c->inf==w&&c->pct<z)
c=c->ant;
elem *q=new elem;
q->inf=w;
q->pct=z;
c->urm->ant=q;
q->urm=c->urm;
q->ant=c;
c->urm=q;
c=q;
}
else
{
if(c->inf<w)
{
while(c->inf<w)
c=c->urm;
while(c->inf==w&&c->pct>z)
c=c->urm;
elem *q=new elem;
q->inf=w;
q->pct=z;
c->ant->urm=q;
q->ant=c->ant;
q->urm=c;
c->ant=q;
c=q;
}
else
{
int ok1=0,ok2=0;
while(c->inf==w&&c->pct<z)
{
c=c->ant;
ok1=1;
}
while(c->pct>z&&c->inf==w)
{
c=c->urm;
ok2=1;
}
if(ok1==1||(ok1==0&&ok2==0))
{
elem *q=new elem;
q->inf=w;
q->pct=z;
c->urm->ant=q;
q->urm=c->urm;
q->ant=c;
c->urm=q;
c=q;
}
else
{
elem *q=new elem;
q->inf=w;
q->pct=z;
c->ant->urm=q;
q->ant=c->ant;
q->urm=c;
c->ant=q;
c=q;
}
}
} }
}
f.close();
}
void vector()
{
elem *q=new elem;
q=p;
q=q->urm;long nr;
while(q->urm)
{
nr=0; x=q->inf;
while(q&&q->inf==x)
{
if(nr<x+1)
{
a[n1].pt=q->pct;
a[n1++].nrv=q->inf;
}
nr++;
q=q->urm;
}
}
}
void sortare()
{
long i,j;
for(i=0;i<n1-1;i++)
for(j=i+1;j<n;j++)
if(a[i].pt<a[j].pt)
{
d=a[i];
a[i]=a[j];
a[j]=d;
}
}
void suma()
{
long i;
s=a[0].pt;
for(i=1;i<=n1;i++)
if(a[i].nrv>=a[i-1].nrv)
s+=a[i].pt;
}
int main()
{
citire();
vector();
n1--;
sortare();
suma();
g<<s<<'\n';
g.close();
return 0;
}