Cod sursa(job #1564534)

Utilizator PopoviciRobertPopovici Robert PopoviciRobert Data 9 ianuarie 2016 19:01:56
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
#include <cstdio>
#define MAXN 100000
#define INF 1000000000000000LL
long long d[MAXN+1],pret[MAXN+1],can[MAXN+1];
int main(){
    FILE*fi,*fout;
    int n,i,t,j;
    long long nr,s,min,sum;
    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]);
    d[1]=pret[1]*can[1];
    for(i=2;i<=n;i++){
        min=INF;
        nr=sum=0;
        for(j=i;j>i-t&&j>=1;j--){
            sum+=can[j];
            if(min>d[j-1]+pret[j]*sum+s*nr)
               min=d[j-1]+pret[j]*sum+s*nr;
            nr=nr+sum;
        }
        d[i]=min;
    }
    fprintf(fout,"%lld" ,d[n]);
    fclose(fi);
    fclose(fout);
    return 0;
}