Cod sursa(job #2036099)

Utilizator NToniBoSSNicolae Tonitza NToniBoSS Data 10 octombrie 2017 12:01:21
Problema Branza Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 0.58 kb
#include <stdio.h>
#include <stdlib.h>
int c[100001],deq[100001];
int main()
{
    int n,s,t,p,u,i,k;
    long long rez;
    freopen("branza.in","r",stdin);
    freopen("branza.out","w",stdout);
    scanf("%d%d%d",&n,&s,&t);
    scanf("%d%d",&c[1],&k);
    p=u=1;
    deq[1]=1;
    rez=c[1]*k;
    for(i=2; i<=n; i++)
    {
        scanf("%d%d",&c[i],&k);
        while(p<=u && deq[p]<i-t)
            p++;
        while(u>=p && c[i]<c[deq[u]]+(i-deq[u])*s)
            u--;
        deq[++u]=i;
        rez+=(long long)(c[deq[p]]+(i-deq[p])*s)*k;
    }
    printf("%lld\n",rez);

    return 0;
}