Pagini recente » Cod sursa (job #3220761) | Cod sursa (job #3200715) | Cod sursa (job #2455912) | Cod sursa (job #2205784) | Cod sursa (job #113261)
Cod sursa(job #113261)
#include <stdio.h>
struct gaina
{
long long n,p;
};
gaina v[100001];
gaina w[100001];
long long n,s,t;
long long gf,gs;
FILE *in=fopen("branza.in","r");
FILE *out=fopen("branza.out","w");
int main()
{
long long i=0,x=0,y=0,tf=0,ts=0;
long long sfff=0;
fscanf(in,"%lld%lld%lld",&n,&s,&t);
fscanf(in,"%lld%lld",&x,&y);
v[0].n=x;
v[0].p=0;
w[0].n=x;
w[0].p=y;
gf=0;
gs=0;
for (i=1; i<n; i++)
{
fscanf(in,"%lld%lld",&x,&y);
if (i-v[gs].p>t)
gs++;
if (gs<=gf)
{
ts=gs;
tf=gf;
while (ts!=tf)
{
if (x> v[(ts+tf)/2].n+s*(i-v[(ts+tf)/2].p))
ts=(ts+tf)/2+1;
else
tf=(ts+tf)/2;
}
if (x>v[ts].n+s*(i-v[ts].p))
{
gf=tf+1;
v[gf].n=x;
v[gf].p=i;
}
else
{
gf=ts;
v[ts].n=x;
v[ts].p=i;
}
}
else
{
gs=0;
gf=0;
v[0].n=x;
v[0].p=i;
}
w[i].n=v[gs].n+s*(i-v[gs].p);
w[i].p=y;
}
for (i=0; i<n; i++)
sfff+=w[i].n*w[i].p;
fprintf(out,"%lld\n",&sfff);
fclose(in);
fclose(out);
return 0;
}