Pagini recente » Cod sursa (job #375473) | Cod sursa (job #1116141) | Cod sursa (job #2774022) | Cod sursa (job #399456) | Cod sursa (job #305149)
Cod sursa(job #305149)
#include<cstdio>
#include<deque>
using namespace std;
#define MAX_N 100003
#define p (Q.front())
#define u (Q.back())
deque<int> Q ;
int a[MAX_N];
int c[MAX_N];
int P[MAX_N];
int S, T, N;
int main()
{
freopen("branza.in","r",stdin);
freopen("branza.out","w",stdout);
scanf("%d%d%d",&N,&S,&T);
int i, val;
for(i=1;i<=N;++i) scanf("%d%d",&c[i], &P[i]);
a[0] = 0;
for(i=1;i<=N;++i)
{
val = c[i] + S * (N-i);
while(!Q.empty() && c[u] + S * (N-u) > val) Q.pop_back();
Q.push_back(i);
a[i] = a[i-1] + P[i] * (c[p] + S * (N-p) - S * (N-i));
if(p == i-T) Q.pop_front();
}
printf("%d\n",a[N]);
return 0;
}