Pagini recente » Cod sursa (job #2219175) | Cod sursa (job #2749596) | Cod sursa (job #3225025) | Cod sursa (job #1603712) | Cod sursa (job #935942)
Cod sursa(job #935942)
#include <fstream>
#include <iostream>
#include <iterator>
#include <deque>
#include <algorithm>
#define MAXN 100002
using namespace std;
long long cost[MAXN];
long long demand[MAXN];
int main()
{
int n, t;
long long s;
fstream fin("branza.in", fstream::in);
fstream fout("branza.out", fstream::out);
fin >> n >> s >> t;
//cout << n << " " << s << " " << t << endl;
for (int i=0; i<n; ++i)
{
fin >> cost[i] >> demand[i];
//cout << cost[i] << " " << demand[i] << endl;
}
long long totalCost = 0;
deque<int> deqStore;
for (int i=0; i<n; ++i)
{
while (!deqStore.empty() && cost[deqStore.back()] + (i - deqStore.back()) * s > cost[i])
{
deqStore.pop_back();
}
deqStore.push_back(i);
if (deqStore.front() < i - t)
{
deqStore.pop_front();
}
//cout << (demand[i] * (cost[deqStore.front()] + (i - deqStore.front()) * s)) << endl;
totalCost += (demand[i] * (cost[deqStore.front()] + (i - deqStore.front()) * s));
}
fout << totalCost << "\n";
return 0;
}