Cod sursa(job #2887679)

Utilizator andlftLefter Andrei andlft Data 9 aprilie 2022 23:50:37
Problema Branza Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <deque>

using namespace std;

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

vector <int> costuri;
vector <int> cerere;
deque <int> deck;

long long cost_total = 0;

int n, s, k;
fin>>n>>s>>k;
int aux;

for(int i = 0; i < n; i++)
{
    fin>>aux;
    costuri.push_back(aux);
    fin>>aux;
    cerere.push_back(aux);
}

for(int i = 0; i < n; i++)
{
    while(!deck.empty() && costuri[deck.back()] + (i-deck.back())*s>costuri[i])
    {
        deck.pop_back(); /// daca ziua curenta este mai avantajoasa ca si cost fata de zilele anterioare
                         /// + taxa de depozitare aferenta acestora, acestea se scot din deque si se pune
                         /// ziua curenta
    }
    deck.push_back(i);

    if(i-deck.front()>=k)
    {
        deck.pop_front();  ///se elimina ziua din stanga deque daca branza facuta
                           ///atunci ar fi prea veche pt ziua curenta, cu toate ca ar avea un cost mic :)
    }

    cost_total += costuri[deck.front()]*cerere[i] + s * (i - deck.front()) * cerere[i];
} ///             ^^^^^pretul de productie^^^^^^^   ^^^^^^pretul pentru depozitare^^^^^
fout<<cost_total;

fin.close();
fout.close();
    return 0;
}