Pagini recente » Cod sursa (job #270825) | Cod sursa (job #75727) | Cod sursa (job #305824) | Cod sursa (job #811558) | Cod sursa (job #2887337)
#include <iostream>
#include <stack>
#include <fstream>
using namespace std;
ifstream in("branza.in");
ofstream out("branza.out");
long long n, s, t, i, pret, cerere, suma, minActual;
deque<pair<long, pair<long, long>>> saptamaniDeq; //<pos, <pret, cerere>>
int main()
{
in >> n >> s >> t;
for(i = 1; i <= n; i++)
{
in >> pret >> cerere;
while(saptamaniDeq.empty() == false && saptamaniDeq.back().first + t < i) //inseamna ca a expirat si eliminam din deq sapt care au termenul depasit
saptamaniDeq.pop_back();
//acum ne raman in deq numai sapt care pot produce pt sapt in care ne aflam acum
while(saptamaniDeq.empty() == false && pret < saptamaniDeq.front().second.first + (i - saptamaniDeq.front().first) * s) //dam pop in fata pana cand nu mai avem un pret mai bun
saptamaniDeq.pop_front();
if(saptamaniDeq.empty() == false && saptamaniDeq.front().second.first + (i - saptamaniDeq.front().first) * s < pret)
minActual = minActual = saptamaniDeq.front().second.first + (i - saptamaniDeq.front().first) * s;
else
minActual = pret;
suma += minActual * cerere;
saptamaniDeq.push_front(make_pair(i, make_pair(pret, cerere)));
}
out<<suma;
return 0;
}