Cod sursa(job #67360)

Utilizator azotlichidAdrian Vladu azotlichid Data 24 iunie 2007 14:20:46
Problema Branza Scor Ascuns
Compilator cpp Status done
Runda Marime 1.78 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];
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;
}