Cod sursa(job #1113795)

Utilizator TarabanDragosTaraban Dragos-Petru TarabanDragos Data 20 februarie 2014 21:59:29
Problema Branza Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.73 kb
#include<cstdio>
struct branza{
    long long p;
    long long c;
}v[101000];
long long n,s,t,i,j,d[2][101000],p,u,nr;
FILE *f,*g;
int main(){
    f=fopen("branza.in","r");
    g=fopen("branza.out","w");
    fscanf(f,"%lld%lld%lld",&n,&s,&t);
    for(i=1;i<=n;i++){
        fscanf(f,"%lld%lld",&v[i].p,&v[i].c);
    }
    nr=v[1].p*v[1].c;
    p=u=1;
    d[0][1]=v[1].p;
    d[1][1]=1;
    for(i=2;i<=n;i++){
        while(u>=p&&d[0][u]*v[i].c+(i-d[1][u])*s*v[i].c>=v[i].p*v[i].c){
            u--;
        }
        d[0][++u]=v[i].p;
        d[1][u]=i;
        if(u-p>=t)
            p++;
        nr+=d[0][p]*v[i].c+(i-d[1][p])*s*v[i].c;
    }
    fprintf(g,"%lld",nr);
    fclose(f);
    fclose(g);
    return 0;
}