Pagini recente » Cod sursa (job #1768357) | Cod sursa (job #382418) | Cod sursa (job #1705621) | Cod sursa (job #244725) | Cod sursa (job #962293)
Cod sursa(job #962293)
#include<stdio.h>
long long v[100000],p[100000];
int coada[100000];
int main()
{
FILE *fin,*fout;
fin=fopen("branza.in","r");
fout=fopen("branza.out","w");
int n,k;
long long s;
fscanf(fin,"%d%d%d",&n,&s,&k);
int i;
for(i=0;i<n;i++)
fscanf(fin,"%d%d",&v[i],&p[i]);
long long S=0,st=1,dr=0;
k++;
for(i=0; i<n; i++)
{
while(st<=dr&&v[i]*p[i]<=(i-coada[dr])*s*p[i]+p[i]*v[coada[dr]])
dr--;
dr++;
coada[dr] = i;
if (coada[st] == i-k)
st++;
S+=(i-coada[st])*s*p[i]+v[coada[st]]*p[i];
}
fprintf(fout,"%lld",S);
return 0;
}