Pagini recente » Cod sursa (job #2365805) | Cod sursa (job #402366) | Cod sursa (job #2959604) | Cod sursa (job #2568744) | Cod sursa (job #359657)
Cod sursa(job #359657)
#include<fstream>
#define dmax 100003
using namespace std;
ifstream in("lupu.in");
ofstream out("lupu.out");
int n,h[dmax],dim;
long long x,l,t,lana;
struct oaie
{ long long d;
long long a;
bool z;
} oi[dmax];
int father(int k)
{ return k/2;
}
void percolate(int n,int k)
{ long long key=oi[h[k]].a,key2=oi[h[k]].d;
int pi=h[k];
while(k>1 && (key>oi[h[father(k)]].a || ( key==oi[h[father(k)]].a && key2>oi[h[father(k)]].d )) )
{ h[k]=h[father(k)];
k=father(k);
}
h[k]=pi;
}
int main()
{ int i,ok,j;
in>>n>>x>>l;
for(i=1;i<=n;i++)
{ in>>oi[i].d>>oi[i].a;
oi[i].z=1;
}
in.close();
while(ok)
{ ok=0;
for(i=1;i<=n;i++)
{ if(oi[i].z==1)
ok=-1;
if(oi[i].d+(t+1)*l>x && oi[i].z==1)
{ ok=1;
dim++;
h[dim]=i;
percolate(dim,dim);
oi[i].z=0;
}
}
if(ok==-1)
{ ok=1;
for(i=1;i<=n;i++)
if(oi[i].z==1)
{ dim++;
h[dim]=i;
percolate(dim,dim);
}
}
if(ok==1)
lana+=oi[h[1]].a;
t++;
dim=0;
}
out<<lana;
out.close();
return 0;
}