Pagini recente » Cod sursa (job #327580) | Cod sursa (job #812453) | Cod sursa (job #82995) | Cod sursa (job #1070520) | Cod sursa (job #1806624)
#include <iostream>
#include <cstdio>
#include <deque>
#define Nmax 100010
using namespace std;
int c[Nmax],p[Nmax];
deque < int > Q;
int n,k,s1=0,s;
void citire()
{
scanf("%d %d %d",&n,&s,&k);
for(int i=1;i<=n;i++)
{
scanf("%d",&c[i]);
scanf("%d",&p[i]);
}
for(int i=1;i<k;i++)
{
while(!Q.empty()&&c[i]<=c[Q.back()]+s*(i-Q.front()))
{
Q.pop_back();
}
Q.push_back(i);
s1+=(c[Q.front()]+s*(i-Q.front()))*p[i];
}
for(int i=k;i<=n;i++)
{
if(Q.front()==(i-k)&&!Q.empty())
Q.pop_front();
while(!Q.empty()&&c[i]<=c[Q.back()]+s*(i-Q.front()))
{
Q.pop_back();
}
Q.push_back(i);
s1+=(c[Q.front()]+s*(i-Q.front()))*p[i];
}
printf("%d",s1);
}
int main()
{
freopen("branza.in","r",stdin);
freopen("branza.out","w",stdout);
citire();
//cout << "Hello world!" << endl;
return 0;
}