Pagini recente » Flux si cuplaj | Cod sursa (job #822878) | Cod sursa (job #734796) | Cod sursa (job #1896085) | Cod sursa (job #67369)
Cod sursa(job #67369)
#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];
int gp[MAXN], price[MAXN], q[MAXN], t[MAXN], qb, qe;
void gen(void)
{
time_t t;
srand((unsigned) time(&t));
FILE *fo = fopen("branza.in", "w");
int N = 40000, S = 7, T = 1234, 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() % 5000, rand() % 10001);
fclose(fo);
}
#define MAX(a, b) (a) > (b) ? (a) : (b)
void brute(void)
{
int newp[MAXN];
int i, j;
for (i = 0; i < N; i ++)
{
newp[i] = C[i];
for (j = MAX(0, i - T); j < i; j ++)
if (C[j] + (i - j) * S < newp[i])
newp[i] = C[j] + (i - j) * S;
}
for (i = 0; i < N; i ++)
if (newp[i] != price[i])
printf("wtf?!\n");
}
int main(void)
{
// gen(); return 0;
freopen("branza.in", "r", stdin);
freopen("branza.out", "w", stdout);
scanf("%d %d %d", &N, &S, &T);
for (i = 0; i < N; i ++)
scanf("%d %d", &(C[i]), &(P[i]));
for (i = 0; i < N; i ++)
gp[i] = C[i] + (N - i) * S;
for (i = qb = 0, qe = -1; i < N; i ++)
{
// remove old prices
for (; qb <= qe && t[qb] + T < i; qb ++);
// add new price
for (; qb <= qe && q[qe] > gp[i]; qe --);
++ qe;
t[qe] = i, q[qe] = gp[i];
// get min price
price[i] = q[qb];
}
for (i = 0; i < N; i ++)
price[i] -= (N - i) * S;
long long sol = 0;
for (i = 0; i < N; i ++)
sol += (long long)price[i] * (long long)P[i];
printf("%lld\n", sol);
return 0;
}