Pagini recente » Cod sursa (job #1847976) | Cod sursa (job #2543587) | Cod sursa (job #1585918) | Cod sursa (job #3179614) | Cod sursa (job #1138668)
#include <fstream>
#include <iostream>
#include <deque>
using namespace std;
int main()
{
ifstream in("branza.in");
ofstream out("branza.out");
int n,t,s;
long long cost[100001], cant[100001];
in >> n >> s >> t;
for( int i=0; i<n; i++ ) {
in >> cost[i] >> cant[i];
}
long long suma = 0;
deque<long long> d;
d.push_back(0);
suma += cant[0]*cost[0];
for( int i=1; i<n; i++) {
while(!d.empty() && cost[i]<cost[d.back()]+s*(i-d.back())) {
d.pop_back();
}
d.push_back(i);
while( i-d.front() > t ) {
d.pop_front();
}
suma += cost[ d.front() ] * cant[i] + cant[i]*s*( i-d.front() );
}
out << suma << '\n';
return 0;
}