Pagini recente » Cod sursa (job #2212389) | Cod sursa (job #1155650) | Cod sursa (job #410749) | Cod sursa (job #2529907) | Cod sursa (job #113288)
Cod sursa(job #113288)
#include <stdio.h>
struct ceva
{
long long p,v;
};
ceva a[100001];
long long s;
long long cauta(long long x,long long p,long long u,long long y)
{
long long m,aux;
while (p<u)
{
m=(p+u)/2;
aux=a[m].v + s*(y-a[m].p);
if (x<=aux)
u=m;
else
p=m+1;
}
if (a[p].v+s*(y-a[p].p)<x)
return p+1;
return p;
}
int main ()
{
FILE *in,*out;
long long cost=0,p,u,n,i,t,x,c;
in=fopen("branza.in","r");
out=fopen("branza.out","w");
fscanf(in,"%lld%lld%lld",&n,&s,&t);
fscanf(in,"%lld%lld",&x,&c);
p=1;
u=1;
a[1].v=x;
a[1].p=1;
cost+=a[p].v*c;
for (i=2;i<=n;i++)
{
fscanf(in,"%lld%lld",&x,&c);
if (i-a[p].p+1>t)
p++;
t=cauta(x,p,u,i);
a[t].v=x;
a[t].p=i;
cost+=(a[p].v+s*(i-a[p].p))*c;
u=t;
}
fprintf(out,"%lld\n",cost);
fclose(in);
fclose(out);
return 0;
}