Pagini recente » Cod sursa (job #3145991) | Cod sursa (job #3247065) | Cod sursa (job #1640099) | Cod sursa (job #29073) | Cod sursa (job #67390)
Cod sursa(job #67390)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#define MAXN 100005
int N, S, T, i, j, k;
int C[MAXN], P[MAXN], newp[MAXN];
void gen(void)
{
time_t t;
srand((unsigned) time(&t));
FILE *fo = fopen("branza.in", "w");
int N = 10, S = 2, T = 3, i;
// int N = 10, S = 5, T = 4, i;
fprintf(fo, "%d %d %d\n", N, S, T);
for (i = 0; i < N; i ++)
fprintf(fo, "%d %d\n", 1 + rand() % 11, 1+rand() % 11);
fclose(fo);
}
#define MAX(a, b) (a) > (b) ? (a) : (b)
int main(void)
{
// gen(); return 0;
freopen("branza.in", "r", stdin);
freopen("branza.out", "w", stdout);
scanf("%d %d %d", &N, &S, &T);
int i, j;
for (i = 0; i < N; i ++) scanf("%d %d", &C[i], &P[i]);
for (i = 0; i < N; i ++)
{
newp[i] = C[i];
for (j = MAX(0, i - T), j = MAX(j, i-5000); j < i /*&& i-j < 12000*/; j ++)
// for (j = i-1; j>=0 && j>=i-T && i-j < 2000; j --)
if (C[j] + (i - j) * S < newp[i])
newp[i] = C[j] + (i - j) * S;
}
long long sol = 0;
for (i = 0; i < N; i ++)
sol += (long long)newp[i] * (long long)P[i];
printf("%lld\n", sol);
return 0;
}