Pagini recente » Cod sursa (job #709459) | Cod sursa (job #3280213) | Cod sursa (job #1772127) | Cod sursa (job #1239041) | Cod sursa (job #17462)
Cod sursa(job #17462)
#include <stdio.h>
#define input "lupu.in"
#define output "lupu.out"
#define nmax 200002
struct oaie {long long d,c,t;} o[nmax],aux,s1[nmax],s2[nmax],vect[nmax];
long long n,x,l,sol,l1,l2,j,i1,i2,nl,pc,t,timp,nm;
void citire()
{
long i;
FILE *fin;
fin=fopen(input,"r");
fscanf(fin,"%lld %lld %lld",&n,&x,&l); nm=0;
for (i=1;i<=n;i++)
{
nm++;
fscanf(fin,"%lld %lld",&o[nm].d,&o[nm].c);
o[nm].t=1+(x-o[nm].d)/l;
if (o[nm].d>x) nm--;
}
fclose(fin);
}
void afisare()
{
FILE *fout;
fout=fopen(output,"w");
fprintf(fout,"%lld",sol);
fclose(fout);
}
void merge(long ls, long ld)
{
if (ls<ld)
{
long k=(ls+ld)/2,kk;
merge(ls,k);
merge(k+1,ld);
l1=0;
l2=0;
for (j=ls;j<=k;j++) s1[++l1]=o[j];
for (j=k+1;j<=ld;j++) s2[++l2]=o[j];
i1=1;
i2=1;
k=ls-1;
while (i1<=l1&&i2<=l2)
if (s1[i1].t<s2[i2].t) o[++k]=s2[i2++];
else o[++k]=s1[i1++];
for (kk=i1;kk<=l1;kk++) o[++k]=s1[kk];
for (kk=i2;kk<=l2;kk++) o[++k]=s2[kk];
}
}
void urca(long x)
{
if (vect[x].c>vect[x/2].c&&x>1)
{
aux=vect[x];
vect[x]=vect[x/2];
vect[x/2]=aux;
urca(x/2);
}
}
void adauga()
{
vect[++nl]=o[pc];
urca(nl);
}
void scoatecap(long k)
{
if (((vect[2*k].c)||(vect[2*k+1].c))&&(k<=nl))
if (vect[2*k+1].c>vect[2*k].c)
{
aux=vect[k];
vect[k]=vect[2*k+1];
vect[2*k+1]=aux;
scoatecap(2*k+1);
}
else
{
aux=vect[k];
vect[k]=vect[2*k];
vect[2*k]=aux;
scoatecap(2*k);
}
}
void solve()
{
merge(1,n);
nl=0;
timp=o[1].t; pc=1; sol=0;
while (timp)
{
while (o[pc].t==timp) {adauga(); pc++;}
sol+=vect[1].c;
vect[1].c=0;
scoatecap(1);
timp--;
}
}
int main()
{
citire();
solve();
afisare();
return 0;
}