Cod sursa(job #323932)

Utilizator taloibogdanTaloi Bogdan Cristian taloibogdan Data 14 iunie 2009 10:32:31
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.56 kb
#include<stdio.h>  
struct branza{long long s,i;}a[100500];  
long long n,s,t,st,dr,i;  
long long cc,ca,ss,S;  
int main()  
{  
 freopen("branza.in","r",stdin);  
 freopen("branza.out","w",stdout);  
 scanf("%lld%lld%lld",&n,&s,&t);  
 st=1;  
 dr=0;  
 for(i=1;i<=n;++i)  
    {scanf("%lld%lld",&cc,&ca);  
     ss=cc+(n-i)*s;  
     while(dr>=st&&a[dr].s>ss)--dr;
     a[++dr].s=ss;  
     a[dr].i=i;  
     while(a[st].i<i-t&&st<=dr)++st;  
     ss=a[st].s;  
     ss-=((n-i)*s);  
     S+=(ss*ca);}  
 printf("%lld\n",S);  
 return 0;  
}