Cod sursa(job #154750)

Utilizator perticas_catalinperticas catalin perticas_catalin Data 11 martie 2008 13:55:20
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 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 c[maxn],p[maxn],cer[maxn],cerp[maxn],n,s,t,cmin[maxn],deque[maxn],ind[maxn];
int main()
{
  int i,st,dr,j;
  long long v1,v2;
  fscanf(fin,"%lld%lld%lld",&n,&s,&t);
  cer[0]=0;cerp[0]=0;
  for(i=1;i<=n;i++)
  {
    fscanf(fin,"%lld%lld",&c[i],&p[i]);
    cer[i]=cer[i-1]+p[i];
    cerp[i]=cerp[i-1]+p[i]*i;
  }
  fclose(fin);
  st=dr=0;
  deque[0]=inf;
  ind[0]=0;
  cmin[0]=0;
  for(i=1;i<=n;i++)
  {
    if(ind[st]<i-t) st++;
    v1=deque[st]-(cerp[n]-cerp[i])*s+(cer[n]-cer[i])*ind[st]*s+(cer[i]-cer[ind[st]])*c[ind[st]];
    v2=cmin[i-1]+c[i]*p[i];
    cmin[i]=min(v1,v2);
    j=dr;
    v1=cmin[i]+(cerp[n]-cerp[i])*s-(cer[n]-cer[i])*i*s;
    while(deque[j]>v1&&j>=st) j--;
    dr=j+1;
    deque[dr]=v1;
    ind[dr]=i;
  }
  fprintf(fout,"%lld",cmin[n]);
  fclose(fout);
  return 0;
}