Pagini recente » Cod sursa (job #714740) | Cod sursa (job #1846912) | Cod sursa (job #2880972) | Cod sursa (job #1672343) | Cod sursa (job #1806602)
#include <iostream>
#include <cstdio>
#define Nmax 100010
#include <deque>
using namespace std;
deque <int> deq;
pair<int,int> vec[Nmax];
long long 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("%lld %lld %lld",&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;
}