Cod sursa(job #73978)

Utilizator astronomyAirinei Adrian astronomy Data 23 iulie 2007 11:29:32
Problema Branza Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 0.77 kb
#include <stdio.h>
#include <string.h>

#define MAX_N 100100

typedef long long llong;

int N, S, T, Q[MAX_N], Poz[MAX_N];
llong res;

llong solve(void)
{
    int i, c, p, inc, sf;

    scanf("%d %d %d\n", &N, &S, &T);
    
    scanf("%d %d\n", &c, &p), Q[inc = sf = 0] = c, Poz[inc] = 1;
    res += (llong)c*p;

    for(i = 2; i <= N; i++)
    {
        scanf("%d %d\n", &c, &p);
        for(; sf >= inc && c <= Q[sf]+S*(i-Poz[sf]); sf--) ;
        Q[++sf] = c, Poz[sf] = i;
        for(; i-Poz[inc] > T; inc++) ;
        res += (llong)(Q[inc]+S*(i-Poz[inc]))*p;
    }

    return res;
}

int main(void)
{
    freopen("branza.in", "rt", stdin);
    freopen("branza.out", "wt", stdout);

    printf("%lld\n", solve());

    return 0;
}