Pagini recente » Cod sursa (job #1024085) | Cod sursa (job #786505) | Cod sursa (job #1054713) | Cod sursa (job #2269084) | Cod sursa (job #2887679)
#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;
}