Cod sursa(job #1394312)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 20 martie 2015 10:53:15
Problema Branza Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 0.69 kb
#include <stdio.h>
#define MAXN 100000
int v[MAXN], d[MAXN];
int main(){
    int n, s, t, p, st, dr, i;
    long long ans;
    FILE *fin, *fout;
    fin=fopen("branza.in", "r");
    fout=fopen("branza.out", "w");
    fscanf(fin, "%d%d%d%d%d", &n, &s, &t, &v[0], &p);
    d[st=0]=0;
    dr=1;
    ans=p*(long long)v[0];
    for(i=1; i<n; i++){
        fscanf(fin, "%d%d", &v[i], &p);
        if(d[st]<i-t){
            st++;
        }
        while((dr>st)&&(v[d[dr-1]]+s*(i-d[dr-1])>v[i])){
            dr--;
        }
        d[dr++]=i;
        ans+=p*(long long)(v[d[st]]+s*(i-d[st]));
    }
    fprintf(fout, "%lld\n", ans);
    fclose(fin);
    fclose(fout);
    return 0;
}