Cod sursa(job #67806)

Utilizator mariusdrgdragus marius mariusdrg Data 25 iunie 2007 17:22:22
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.71 kb
#include<stdio.h>

const long long maxn = 100001;

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

int main()
{
        freopen("branza.in","r",stdin);
                freopen("branza.out","w",stdout);
                        scanf("%lld %lld %lld",&n,&s,&t);
                                for(i = 1;i <= n; ++i)
                                        {
                                                        scanf("%lld %lld",&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;
                                                                                                                                                                                                                                                                                                                }