Pagini recente » Cod sursa (job #2766812) | Cod sursa (job #1784159) | Cod sursa (job #2890486) | Cod sursa (job #2471486) | Cod sursa (job #2973998)
#include <bits/stdc++.h>
using namespace std;
int n,s,t,cost[10000005],kil[10000005],suma;
deque<int> dechiu;
int main()
{
ifstream cin("branza.in");
ofstream cout("branza.out");
cin >> n >> s >> t;
for(int i=1;i<=n;i++)
{
cin >> cost[i] >> kil[i];
}
for(int i=1;i<=n;i++)
{
while(!dechiu.empty() && cost[i] < (cost[dechiu.back()] + s*(i-dechiu.back()))) // elementele mici scot elementele mari, calculam si pt depozity
{
dechiu.pop_back();
}
dechiu.push_back(i);
if(!dechiu.empty() && dechiu.front() == i-t-1)
{
dechiu.pop_front(); //nu se afla intr-un interval bun pentru depozit
}
suma += kil[i] * (cost[dechiu.front()] + s*(i-dechiu.front()));
}
cout << suma;
}