Pagini recente » Cod sursa (job #2104671) | Cod sursa (job #1799039) | Cod sursa (job #2330606) | Cod sursa (job #3275859) | Cod sursa (job #825248)
Cod sursa(job #825248)
#include <fstream>
#include <deque>
using namespace std;
ifstream f("branza.in");
ofstream g("branza.out");
int n,t,s;
long long cost[100001];
long long cant[100001];
int main(){
f>>n>>s>>t;
for(int i=0; i<n; ++i)
f>>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());
}
g<<suma;
return 0;
}