Cod sursa(job #68333)

Utilizator pauldbPaul-Dan Baltescu pauldb Data 27 iunie 2007 16:32:30
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.63 kb
#include <stdio.h>

#define maxn 100010
#define ll long long
#define maxv 10000000

int n,t,s,p,r;
int a[maxn],b[maxn],d[maxn];
ll sol;

int main()
{
    freopen("branza.in","r",stdin);
    freopen("branza.out","w",stdout);
    
    scanf("%d %d %d ",&n,&s,&t);
    
    int i;
    
    for (i=1;i<=n;i++) scanf("%d %d ",&a[i],&b[i]);
    a[0]=maxv;
    
    for (i=1;i<=n;i++)
    {
        while ((p<=r) && ((i-d[r])*s+a[d[r]]>a[i])) r--;
        r++;
        d[r]=i;
        
        sol+=1LL*b[i]*((i-d[p])*s+a[d[p]]);
        if (i-t==d[p]) p++;
    }
    
    printf("%lld\n",sol);
    
    return 0;
}