Pagini recente » Cod sursa (job #2893830) | Cod sursa (job #403201) | Cod sursa (job #1235309) | Cod sursa (job #1233382) | Cod sursa (job #1806596)
#include <iostream>
#include <cstdio>
#define Nmax 100010
#include <deque>
using namespace std;
deque <int> deq;
pair<int,int> vec[Nmax];
int n,s,t;
long long cost;
int compare(int i)
{
long long cost1 ,cost2;
cost1 = vec[i].first;
cost2 = vec[deq.back()].first + s * (i-deq.back());
if(cost1 < cost2)
return 1;
else
return 0;
}
void read()
{
freopen("branza.in","r",stdin);
freopen("branza.out","w",stdout);
scanf("%d %d %d",&n,&s,&t);
for(int i = 1 ; i < t ; i++)
{
scanf("%d %d",&vec[i].first,&vec[i].second);
while(!deq.empty() && compare(i) == 1)
deq.pop_back();
deq.push_back(i);
cost += (vec[deq.front()].first + s*(i - deq.front()))*vec[i].second;
}
for(int i = t ; i <= n ; i++)
{
scanf("%d %d",&vec[i].first,&vec[i].second);
if(!deq.empty() && deq.front() <= i - t)
deq.pop_front();
while(!deq.empty() && compare(i) == 1)
deq.pop_back();
deq.push_back(i);
cost += (vec[deq.front()].first + s*(i - deq.front()))*vec[i].second;
}
}
int main()
{
read();
printf("%lld",cost);
return 0;
}