Cod sursa(job #122554)

Utilizator alexeiIacob Radu alexei Data 12 ianuarie 2008 20:24:40
Problema Branza Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 kb
#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;
}