Cod sursa(job #2475911)

Utilizator SoranaAureliaCatrina Sorana SoranaAurelia Data 17 octombrie 2019 19:20:52
Problema Branza Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.67 kb
#include <fstream>
#include <deque>
using namespace std;

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

int n, s, t;
int c, p;

struct produs{
    int val, poz;
};

deque <produs>D;

void adaug(int i){
    int mom = c*p;
    while(!D.empty() && p*D.back().val + p*(i-D.back().poz)*s > mom) ///prea scump pt moment
        D.pop_back();
    D.push_back({c, i});

}

int main()
{
    f>>n>>s>>t;
    int rez = 0;
    for(int i=1; i<=n; i++){
        f>>c>>p;
        if(i>t && D.front().poz == i-t-1)
            D.pop_front();
        adaug(i);
        rez = rez + (p * D.front().val + p*(i-D.front().poz)*s);
    }
    g<<rez;
    return 0;
}