Cod sursa(job #2888516)

Utilizator kanyjmkSabau Eduard kanyjmk Data 11 aprilie 2022 15:28:46
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <iostream>
#include <fstream>
#include <deque>
#include <vector>
using namespace std;
ifstream fin("branza.in");
ofstream fout("branza.out");
int main()
{
    int n, s, t;
    long long cost_minim = 0;
    vector <int> cost_branza;
    cost_branza.push_back(0);
    deque <int> saptamani;

    fin >> n >> s >> t;
    for(int saptamana = 1; saptamana <= n; saptamana ++)
    {
        long long cost, kg;
        fin >> cost >> kg;
        cost_branza.push_back(cost);

        while(!saptamani.empty() && saptamani.front() < saptamana - t)
            saptamani.pop_front();

        while(!saptamani.empty() && cost_branza[saptamana] < cost_branza[saptamani.back()] + s * (saptamana-saptamani.back()))
            saptamani.pop_back();

        saptamani.push_back(saptamana);

        cost_minim += kg * (cost_branza[saptamani.front()] + s * (saptamana - saptamani.front()));
    }

    fout << cost_minim;
    return 0;
}