Pagini recente » Cod sursa (job #1460411) | Cod sursa (job #667674) | Cod sursa (job #2374432) | Cod sursa (job #1525826) | Cod sursa (job #208287)
Cod sursa(job #208287)
#include <cstdio>
#include <algorithm>
using namespace std;
long n,t,s,c[100100],p[100100],m[100100];
long i,j,l,u,d[100100],lj,rez;
int main(){
freopen("branza.in","r",stdin);
freopen("branza.out","w",stdout);
scanf("%d%d%d",&n,&s,&t);
for (i=1;i<=n;i++)
scanf("%d%d",&c[i],&p[i]);
l=u=1;
d[1]=1;
m[1]=c[1];
for (i=2;i<=n;i++)
{
lj=i-t;
while ((d[l]<lj)&&(l<=u))
l++;
while (((c[i]+s*(n-i))<(c[d[u]]+s*(n-d[u])))&&(u>=l))
u--;
u++;
d[u]=i;
// printf("%d %d\n",l,u);
// for (j=1;j<=n;j++)
// printf("%d ",d[j]);
// printf("\n\n");
m[i]=c[d[l]]+s*(n-d[l])-s*(n-i);
}
for (i=1;i<=n;i++)
rez+=m[i]*p[i];
printf("%d\n",rez);
//for (i=1;i<=n;i++)
// printf("%d ",m[i]);
return 0;
}