Cod sursa(job #3259160)

Utilizator parrot279Sofi Tudose parrot279 Data 25 noiembrie 2024 13:52:57
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <fstream>
#include <queue>

using namespace std;
ifstream cin("branza.in");
ofstream cout("branza.out");



int main()
{
    deque<pair <long long, long long> > q; //first e costul, second e saptamana
    int n, s, t; //s = taxa, t = nr saptamani
    long long c, p, suma = 0;  // c = cost, p = nr kg
    cin>>n>>s>>t;
    for(int i = 1; i <= n; i++)
    {
        cin>>c>>p;

        if(!q.empty() && q.front().second + 1 == i - t) // se strica branza
        {
            q.pop_front();
        }

        while(!q.empty() && c < q.back().first + s * (i - q.back().second))
        {
            q.pop_back();
        }

        q.push_back(make_pair(c, i));
        suma += (q.front().first + s * (i - q.front().second)) * p;
    }
    cout<<suma;

    return 0;
}