Cod sursa(job #1564579)

Utilizator PopoviciRobertPopovici Robert PopoviciRobert Data 9 ianuarie 2016 19:34:55
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.68 kb
#include <cstdio>
#define MAXN 100000
long long d[MAXN+1],pret[MAXN+1],can[MAXN+1];
int poz[MAXN+1];
int main(){
    FILE*fi,*fout;
    int n,i,t,s,e,b;
    fi=fopen("branza.in" ,"r");
    fout=fopen("branza.out" ,"w");
    fscanf(fi,"%d%d%d" ,&n,&s,&t);
    for(i=1;i<=n;i++)
        fscanf(fi,"%lld%lld" ,&pret[i],&can[i]);
    b=0;
    e=-1;
    for(i=1;i<=n;i++){
        if(poz[b]+t<i)
          b++;
        while(e>=b&&pret[poz[e]]*can[i]+s*(i-poz[e])*can[i]>=pret[i]*can[i])
           e--;
        poz[++e]=i;
        d[i]=d[i-1]+pret[poz[b]]*can[i]+s*(i-poz[b])*can[i];
    }
    fprintf(fout,"%lld" ,d[n]);
    fclose(fi);
    fclose(fout);
    return 0;
}