Cod sursa(job #1794127)

Utilizator FlorinHajaFlorin Gabriel Haja FlorinHaja Data 31 octombrie 2016 22:47:18
Problema Branza Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 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;
int fr, bk, dq[100005];
int pr[100005], cant;

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++;
        //g << dq[fr] << ' ';
        /*if ((cant*pr[dq[fr]] + (i-dq[fr])*pd) < cant*pr[i])
            g << dq[fr] << ' ';
        else g << i << ' ';*/
        min1 = 1e+12;
        for (j = fr; j <= bk; j++)
            min1 = min((unsigned long long)(pr[dq[j]] + (i-dq[j])*pd), min1);
        s += cant*min(min1, (unsigned long long)pr[i]);
    }
    g << s;
    return 0;
}