Cod sursa(job #155305)

Utilizator perticas_catalinperticas catalin perticas_catalin Data 11 martie 2008 20:59:19
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.74 kb
#include<stdio.h>
FILE*fin=fopen("branza.in","r");
FILE*fout=fopen("branza.out","w");
#define maxn 100001
#define inf 1000000000
#define min(a,b)((a)<(b)?(a):(b))
long long rez,c[maxn],p[maxn];
int main()
{
  int i,j,n,s,t,st,dr;
  long long v1,v2,deque[maxn],ind[maxn];
  fscanf(fin,"%d%d%d",&n,&s,&t);
  for(i=1;i<=n;i++)
    fscanf(fin,"%lld%lld",&c[i],&p[i]);
  fclose(fin);
  st=dr=0;
  deque[0]=inf;
  ind[0]=0;
  rez=0;
  for(i=1;i<=n;i++)
  {
    if(ind[st]<i-t) st++;
    v1=p[i]*(deque[st]-(n-i)*s);
    v2=c[i]*p[i];
    rez+=min(v1,v2);
    v1=c[i]+(n-i)*s;
    j=dr;
    while(v1<deque[j]&&j>=st) j--;
    dr=j+1;
    deque[dr]=v1;
    ind[dr]=i;
  }
  fprintf(fout,"%lld",rez);
  fclose(fout);
  return 0;
}