Cod sursa(job #1113794)

Utilizator TarabanDragosTaraban Dragos-Petru TarabanDragos Data 20 februarie 2014 21:57:54
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.7 kb
#include<cstdio>
struct branza{
    int p;
    int c;
}v[101000];
int 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,"%d%d%d",&n,&s,&t);
    for(i=1;i<=n;i++){
        fscanf(f,"%d%d",&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,"%d",nr);
    fclose(f);
    fclose(g);
    return 0;
}