Cod sursa(job #81532)

Utilizator marcelcodreaCodrea Marcel marcelcodrea Data 2 septembrie 2007 20:57:09
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include<stdio.h>
long long n,cant[100001],pret[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;
  pret[0]=1000000000;
  cost[1]=pret[1]*cant[1];
 for(i=2;i<=n;i++)
    {
    if (i>t+1)
       {
       el=i-t-1;
       if (el==poz[cap]) {poz[cap]=0;cap++;}
       while (((cant[i]*pret[poz[coada]]+(i-poz[coada])*s*cant[i])>(pret[i]*cant[i]))&&(coada>cap-1))
            coada--;
         coada++;
        poz[coada]=i;
       cost[i]=cant[i]*pret[poz[cap]]+(i-poz[cap])*s*cant[i];
       }
       else
         {
        while (((cant[i]*pret[poz[coada]]+(i-poz[coada])*s*cant[i])>(pret[i]*cant[i]))&&(coada>cap-1))
            coada--;
        coada++;
        poz[coada]=i;
       cost[i]=cant[i]*pret[poz[cap]]+(i-poz[cap])*s*cant[i];
         }
         
    }
   s=0;
 for(i=1;i<=n;i++)
  s+=cost[i];
  printf("%lld\n",s);
 return 0;
}