Cod sursa(job #80503)

Utilizator marcelcodreaCodrea Marcel marcelcodrea Data 28 august 2007 12:18:16
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include<stdio.h>
long long n,cant[100001],pret[100001],deque[100001],s,t,cost[100001],poz[100001],el,i,cap,coada,aux;
int main()
{
 freopen("branza.in","r",stdin);
 freopen("branza.out","w",stdout);
 scanf("%lld %lld %lld",&n,&s,&t);
 for(i=1;i<=n;i++)
  scanf("%lld %lld",&pret[i],&cant[i]);
  cap=1;
  coada=1;
  poz[cap]=1;
  deque[cap]=pret[1];
  cost[1]=pret[1]*cant[1];
 for(i=2;i<=n;i++)
    {
    if (i>t+1)
       {
       el=pret[i-t-1];
       if (el==deque[cap]) cap++;
       while ((cant[i]*deque[coada]+(i-poz[coada])*s*cant[i])>pret[i]*cant[i])
            coada--;
         coada++;
        deque[coada]=pret[i];
        poz[coada]=i;
       cost[i]=cant[i]*deque[cap]+(i-poz[cap])*s*cant[i];
       }
       else
         {
        while ((cant[i]*deque[coada]+(i-poz[coada])*s*cant[i])>(pret[i]*cant[i])&&coada>0)
            coada--;
        coada++;
        deque[coada]=pret[i];
        poz[coada]=i;
       cost[i]=cant[i]*deque[cap]+(i-poz[cap])*s*cant[i];
         }
         
    }
   s=0;
 for(i=1;i<=n;i++)
  s+=cost[i];
  printf("%lld\n",s);
 return 0;
}