Pagini recente » Cod sursa (job #1571061) | Cod sursa (job #1602185) | Cod sursa (job #1072707) | Cod sursa (job #2338178) | Cod sursa (job #1809204)
#include <iostream>
#include <cstdio>
#include <deque>
#define NMAX 100005
using namespace std;
int N,S,T;
deque<long long> dq;
long long c[NMAX];
logn long p[NMAX];
long long rez=0;
void citire()
{
scanf("%d%d%d",&N,&S,&T);
for(int i=1;i<=N;i++)
scanf("%d%d",&c[i],&p[i]);
}
bool comp(int j, int i)
{
return (i-j)*S+c[j] < c[i];
}
void rezolvare()
{
dq.push_back(1);
rez=c[1]*p[1];
for(int i=2;i<=N;i++)
{
while(!dq.empty() && comp(dq.back(),i)==0)
dq.pop_back();
dq.push_back(i);
if(i-dq.front()+1>T)
dq.pop_front();
rez+=p[i]*((i-dq.front())*S+c[dq.front()]);
}
}
int main()
{
freopen("branza.in","r",stdin);
freopen("branza.out","w",stdout);
citire();
rezolvare();
printf("%lld",rez);
return 0;
}