Pagini recente » Istoria paginii utilizator/greenbud | Cod sursa (job #1387056) | Cod sursa (job #2171256) | Cod sursa (job #1247894) | Cod sursa (job #74944)
Cod sursa(job #74944)
#include<stdio.h>
long long inc,sf,sum,total,i,t,n,s;
struct lol
{
long long p,c;
};
lol x[100001];
struct loldoi
{
long long val,poz;
};
loldoi dq[100001];
int main()
{
freopen ("branza.in","rt",stdin);
freopen ("branza.out","wt",stdout);
scanf("%lld %lld %lld",&n,&s,&t);
for (i=1;i<=n;i++)
scanf("%lld %lld",&x[i].c,&x[i].p);
inc=1;sf=0;
for (i=1;i<=n;i++)
{
sum=x[i].c;
sum+=(n-i)*s;
while (sf>=inc && sum<=dq[sf].val) sf--;
dq[++sf].val=sum,dq[sf].poz=i;
if (sf>t+1) inc++;
total+=(long long)(dq[inc].val-(n-dq[inc].poz)*s)*x[i].p+(i-dq[inc].poz)*s*x[i].p;
}
printf("%lld\n",total);
return 0;
}