Cod sursa(job #2889177)

Utilizator TindecheTindeche Alexandru Tindeche Data 12 aprilie 2022 13:42:39
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <string.h>
#include <fstream>
#include <deque>

using namespace std;

ifstream fin("branza.in");
ofstream fout("branza.out");

int main ()
{
    long long n, s, t;
    long long sapt[1000001];
    deque <long long> dq;
    long long suma = 0;
    fin >> n >> s >> t; // Citesc nr de saptamani, suma pentru stocarea unui kg de braza,
    for(int i = 0; i < n; i++)
    {
        long long q;
        fin >> sapt[i] >> q;
        while(!dq.empty() && dq.front() < i - t)
            dq.pop_front();
        /*
         * Este mai eficient sa luam branza din saptamana curenta daca este mai bine decat pretul per
         * un kg din saptamanile precedente + cate saptamani ar trebui sa depozitez branza aceea * pretul per sapt
         */
        while(!dq.empty() && sapt[i] < ((i - dq.back()) * s + sapt[dq.back()]))
            dq.pop_back();
        // Adaugam ziua curenta
        dq.push_back(i);
        suma = suma + q * (sapt[dq.front()] + (i - dq.front()) * s);
    }
    fout << suma;
    return 0;
}