Cod sursa(job #2044792)

Utilizator borscalinCalin-Stefan Georgescu borscalin Data 21 octombrie 2017 13:49:09
Problema Branza Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 0.69 kb
#include <stdio.h>
#include <stdlib.h>
#define NMAX 100000

int d[1 + NMAX];
int v[1 + NMAX];

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