Pagini recente » Cod sursa (job #1942256) | Cod sursa (job #525159) | Cod sursa (job #2950021) | Cod sursa (job #1285350) | Cod sursa (job #67972)
Cod sursa(job #67972)
#include<stdio.h>
#define Nm 100000
int C[Nm],P[Nm],n,s,t;
unsigned long long Cm[Nm];
void read()
{
int i;
freopen("branza.in","r",stdin);
scanf("%d%d%d",&n,&s,&t);
for(i=0;i<n;++i)
scanf("%d%d",C+i,P+i);
}
void solve()
{
int Val[Nm],Poz[Nm],l=0,r=0,i;
Cm[0]=(unsigned long long)C[0]*P[0]; Val[0]=C[0]; Poz[0]=0;
for(i=1;i<n;++i)
{
while(l<=r && C[i]<=Val[r]+s*i)
--r;
Val[++r]=C[i]-s*i; Poz[r]=i;
if(Poz[l]==i-t-1)
++l;
Cm[i]=Cm[i-1]+(Val[l]+s*i)*(unsigned long long)P[i];
}
}
void write()
{
freopen("branza.out","w",stdout);
printf("%llu\n",Cm[n-1]);
}
int main()
{
read();
solve();
write();
return 0;
}