Cod sursa(job #956331)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 2 iunie 2013 21:07:18
Problema Branza Scor 40
Compilator c Status done
Runda Arhiva de probleme Marime 0.73 kb
#include <stdio.h>
#define LL long long
int d[10000000],v[10000000];
LL k,s,n,st,dr,a;
LL calc2(LL q){
    return v[d[st]]+(a*(q-d[st]));
}
LL calc1(LL q){
    return v[d[dr]]+(a*(q-d[dr]));
}
LL stanga(LL i){
    if(i-d[st]==k){
        st++;
    }
}
void dreapta(LL i){
    while((st<=dr)&&(v[i]<=calc1(i))){
        dr--;
    }
}
int main(){
    LL i,j,x,s=0;
    FILE *fin,*fout;
    fin=fopen("branza.in","r");
    fout=fopen("branza.out","w");
    fscanf(fin,"%lld%lld%lld",&n,&a,&k);
    i=0;
    st=1;
    while(i<n){
        i++;
        fscanf(fin,"%lld%lld",&v[i],&x);
        stanga(i);
        dreapta(i);
        dr++;
        d[dr]=i;
        s+=x*calc2(i);
    }
    fprintf(fout,"%lld",s);
}