Pagini recente » Cod sursa (job #1733878) | Cod sursa (job #140358) | Cod sursa (job #1240683) | Cod sursa (job #112195) | Cod sursa (job #122554)
Cod sursa(job #122554)
#include<stdio.h>
#define nmax 100000
long long pret[nmax],cerere[nmax],coada[nmax],sol[nmax];
int main()
{
freopen("branza.in","r",stdin);
freopen("branza.out","w",stdout);
int n,s,t,p=1,u=1;
scanf("%d%d%d",&n,&s,&t);
int i,j;
for(i=1; i<=n; ++i)
{scanf("%d%d",&pret[i],&cerere[i]);
sol[i]=pret[i]*cerere[i];
}
coada[1]=1;
long long aux;
long long solutie=sol[1],sum;
for(i=2; i<=n; ++i)
{
sum=sol[i];
for(j=p; j<=u; ++j)
{
aux=cerere[i]*pret[coada[j]]+s*cerere[i]*(i-j);
if(aux<sum){
sum=aux; p=j;}
}
coada[++u]=i;
if(sol[i]==sum)
p=u;
else
if(i+1-coada[p]>t)
++p;
solutie+=sum;
}
printf("%lld\n",solutie);
return 0;
}