Cod sursa(job #1794129)

Utilizator FlorinHajaFlorin Gabriel Haja FlorinHaja Data 31 octombrie 2016 22:51:01
Problema Branza Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.63 kb
#include <fstream>

using namespace std;

ifstream f("branza.in");
ofstream g("branza.out");

int n, i, j, pd, t;
unsigned long long s, min1, pr[100005], cant;
int fr, bk, dq[100005];

int main() {
    f >> n >> pd >> t;
    fr = 1, bk = 0;
    for (i = 1; i <= n; i++) {
        f >> pr[i] >> cant;
        while (fr <= bk && pr[dq[bk]] >= pr[i])
            bk--;
        dq[++bk] = i;
        if (dq[fr] == i-t)
            fr++;

        min1 = 1e+12;
        for (j = fr; j <= bk; j++)
            min1 = min((pr[dq[j]] + (i-dq[j])*pd), min1);
        s += cant*min(min1, pr[i]);
    }
    g << s;
    return 0;
}