Pagini recente » Cod sursa (job #394722) | Cod sursa (job #2698910) | Cod sursa (job #679356) | Cod sursa (job #905924) | Cod sursa (job #216729)
Cod sursa(job #216729)
# include <cstdio>
using namespace std;
# define FIN "branza.in"
# define FOUT "branza.out"
# define min(a,b) (a<b?a:b);
# define MAXN 100010
long long N,T,S,i,j,f,l,A;
long long Stack[MAXN];
long long LowC[MAXN];
long long C[MAXN]; // cantitate
long long P[MAXN]; // pret
int main()
{
freopen(FIN,"r",stdin);
freopen(FOUT,"w",stdout);
scanf("%lld%lld%lld",&N,&S,&T);
for (i = 1; i <= N; ++i)
scanf("%lld%lld",&P[i],&C[i]);
f = l = 1;
LowC[1] = P[1];
Stack[1] = 1;
for (i = 2; i <= N; ++i)
{
A = i-T > 1 ? i-T : 1;
while (Stack[f] < A) f++;
LowC[i] = min(P[Stack[f]] + (i-Stack[f])*S,P[i]);
while (P[Stack[l]]+(N-Stack[l])*S>=P[i]+(N-i)*S && l>=f)
l--;
Stack[++l] = i;
}
A = 0;
for (i = 1; i <= N; ++i)
A += LowC[i] * C[i];
printf("%lld",A);
return 0;
}