Pagini recente » Cod sursa (job #3144083) | Cod sursa (job #2861874) | Cod sursa (job #2133640) | Cod sursa (job #2907265) | Cod sursa (job #93089)
Cod sursa(job #93089)
#include <stdio.h>
#define NMAX 100100
#define MIN(a,b) (((a)<(b))?(a):(b))
int N, T, S, Poz[NMAX];
long long C[NMAX], P[NMAX], A[NMAX], B[NMAX], DQ[NMAX];
void read()
{
int i;
freopen("branza.in", "r", stdin);
scanf("%d%d%d", &N, &S, &T);
for (i = 0; i < N; i++)
scanf("%lld%lld", P+i, C+i);
}
void solve()
{
int i, lo, hi, c;
DQ[0] = P[0]; A[0] = P[0]*C[0];
for (lo = 0, hi = 1, i = 1; i < N; i++)
{
if (i-Poz[lo]>T) lo++;
A[i] = A[i-1]+C[i]*MIN( (DQ[lo]+S*(i-Poz[lo])), P[i] );
c = P[i];
while ( (hi>lo)&&( (DQ[hi-1]+S*(i-Poz[hi-1]))>c ) ) hi--;
DQ[hi] = c; Poz[hi++] = i;
}
}
void brut()
{
int i, j, x;
B[0] = C[0]*P[0];
for (i = 1; i < N; i++)
{
B[i] = B[i-1]+P[i]*C[i];
x = i-T-1;
if (x<0) x = 0;
for (j = x; j < i; j++)
B[i] = MIN(B[i], B[i-1]+C[i]*(P[j]+S*(i-j)));
}
}
void write()
{
freopen("branza.out", "w", stdout);
printf("%lld\n", A[N-1]);
//freopen("brut.out", "w", stdout);
//printf("%lld\n", B[N-1]);
}
int main()
{
read();
solve();
//brut();
write();
return 0;
}