Cod sursa(job #67374)

Utilizator azotlichidAdrian Vladu azotlichid Data 24 iunie 2007 14:58:56
Problema Branza Scor Ascuns
Compilator cpp Status done
Runda Marime 1.23 kb
#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 = 80909, S = 3, T = 32767, 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() % 10000001, 1+rand() % 10000001);
    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 < i && i-j < 10000; j ++) */
        for (j = i-1; j>=0 && j>=i-T && i-j < 10000; 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;
}