Cod sursa(job #67533)

Utilizator mariusdrgdragus marius mariusdrg Data 25 iunie 2007 11:18:47
Problema Branza Scor 0
Compilator cpp Status done
Runda preONI 2007, Runda Finala, Clasa a 10-a Marime 0.92 kb
#include<stdio.h>

const int maxn = 100001;

int i;
int st[maxn];
int co[maxn];
int can[maxn];
int n;
long long din[maxn];
int s;
int t;
int a[maxn];
int b,l;

int main()
{
        freopen("branza.in","r",stdin);
        freopen("branza.out","w",stdout);
        scanf("%d %d %d",&n,&s,&t);
        for(i = 1;i <= n; ++i)
        {
                scanf("%d %d",&co[i],&can[i]);
        }
        b = 1;
        for(i = 1;i <= n; ++i)
        {
                while(i - st[b] > t && b < l)
                {
                        ++b;
                }
                while(co[i] < co[st[l]] + (i - st[l]) * s && l >= b)
                {
                        --l;
                }
                ++l;
                st[l] = i;
                din[i] = din[i - 1] + can[i] * co[st[b]] + (long long)can[i] * s  * (i - st[b]);
        }
        printf("%lld\n",din[n]);
        return 0;
}