Cod sursa(job #1294241)

Utilizator Vlad_317Vlad Panait Vlad_317 Data 17 decembrie 2014 09:54:41
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.62 kb
#include <stdio.h>

const int N=1<<17;

int c[N],p[N],dq[N],t,s,st=1,dr=0;

void stanga(int i)
{
    if (i-dq[st]>t)
        ++st;
}

void dreapta(int i)
{
    while (st<=dr && c[dq[dr]]+(i-dq[dr])*s>=c[i])
        dr--;
    dq[++dr]=i;
}

int main()
{
    freopen("branza.in","r",stdin);
    freopen("branza.out","w",stdout);

    int n;
    scanf("%d%d%d",&n,&s,&t);


    long long s1=0;
    for (int i=1;i<=n;i++)
    {
        scanf("%d%d",&c[i],&p[i]);
        stanga(i);
        dreapta(i);
        s1+=(long long)(c[dq[st]]+(i-dq[st])*s)*p[i];
    }
    printf("%lld",s1);
    return 0;
}