Cod sursa(job #2068184)

Utilizator onoflorinFlorin Onofrei onoflorin Data 17 noiembrie 2017 12:34:36
Problema Branza Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 0.7 kb
#include <stdio.h>
#include <stdlib.h>

int c[100001], d[100001], p[100001];
int main()
{
    FILE *fin, *fout;
    int n, s, t, i, st, dr;
    long long int sum;
    fin=fopen("branza.in", "r");
    fout=fopen("branza.out", "w");
    fscanf(fin, "%d %d %d\n", &n, &s, &t);
    st=0;
    dr=-1;
    sum=0;
    t++;
    for(i=0; i<n; i++)
        fscanf(fin, "%d %d\n", &c[i], &p[i]);
    for(i=0; i<n; i++)
    {
        while(st<=dr && d[st]==i-t)
            st++;
        while(st<=dr && c[i]<=c[d[dr]]+s*(i-d[dr]))
            dr--;
        d[++dr]=i;
        sum = sum + p[i] * (c[d[st]] + (long long) s * (i-d[st]) );
    }
    fprintf(fout, "%lld", sum);
    fclose(fin);
    fclose(fout);
    return 0;
}