Pagini recente » Cod sursa (job #1226526) | Cod sursa (job #2939004) | Cod sursa (job #2657369) | Cod sursa (job #378910) | Cod sursa (job #825600)
Cod sursa(job #825600)
#include <stdio.h>
#include <deque>
#define NMax 100010
using namespace std;
typedef long long ll;
const char IN[]="branza.in",OUT[]="branza.out";
int N,S,T;
ll P[NMax],C[NMax];
ll D[NMax];
deque<int> d;
void add(int x)
{
while (!d.empty() && (x-d.back()>T || C[x]-S*x<C[d.back()]-S*d.back()))
d.pop_back();
d.push_back(x);
while (!d.empty() && (x-d.front()>T))
d.pop_front();
}
void solve()
{
int i;
D[1]=P[1]*C[1];
add(1);
for (i=2;i<=N;++i)
{
add(i);
D[i]=D[i-1]+P[i]*S*i+P[i]*(C[d.front()]-S*d.front());
}
}
int main()
{
int i,p,c;
freopen(IN,"r",stdin);
scanf("%d%d%d",&N,&S,&T);
for (i=1;i<=N;++i) scanf("%d%d",&c,&p),P[i]=p,C[i]=c;
fclose(stdin);
solve();
freopen(OUT,"w",stdout);
printf("%lld\n",D[N]);
fclose(stdout);
return 0;
}