Cod sursa(job #1794131)

Utilizator FlorinHajaFlorin Gabriel Haja FlorinHaja Data 31 octombrie 2016 22:54:22
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.64 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-1)
            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;
}