Cod sursa(job #133356)

Utilizator bogdanhm999Casu-Pop Bogdan bogdanhm999 Data 8 februarie 2008 13:05:05
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.69 kb
#include <stdio.h>

long n,i,s,t,c[100002],p[100002];
long que[100002],poz[100002],s1,s2;
long long sol,m[100002];

int main(){
    freopen("branza.in","r",stdin);
    freopen("branza.out","w",stdout);
    
    scanf("%ld %ld %ld",&n,&s,&t);
    for (i=1;i<=n;i++)
        scanf("%ld %ld",&c[i],&p[i]);
    
    s1=1;s2=0;
    for (i=1;i<=n;i++){
        while (que[s2]+s*(i-poz[s2])>c[i]&&s2>=s1)s2--;
        s2++;
        que[s2]=c[i];
        poz[s2]=i;
        while (i-poz[s1]>t&&s1<s2)s1++;
        m[i]=(long long)que[s1]+(long long)(i-poz[s1])*s;
    }
    
    for (i=1;i<=n;i++)
        sol=(long long)sol+m[i]*p[i];
    
    printf("%lld\n",sol);
    
return 0;
}