Cod sursa(job #2031609)

Utilizator eragon0502Dumitrescu Dragos eragon0502 Data 3 octombrie 2017 16:36:44
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.73 kb
#include <cstdio>

using namespace std;

struct ceva{
int x,i;
}dq[100005];

int c[100005];
int p[100005];

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

    int  n,tx,t;
    long long s=0;

    scanf("%d %d %d ",&n,&tx,&t);

    for(int i=1;i<=n;++i)
    {
        scanf("%d %d",&c[i],&p[i]);
        c[i]-=tx*i;
    }

    int st=1,dr=1;
    s=(c[1]+tx)*p[1];
    dq[1].x=c[1];
    dq[1].i=1;

    for(int i=2;i<=n;++i)
    {
        while(dq[dr].x>c[i]&&dr>=st)
        {
            dr--;
        }
        dq[++dr].x=c[i];
        dq[dr].i=i;
        if(i-dq[st].i>t)
            st++;
        s+=((dq[st].x+tx*dq[st].i+tx*(i-dq[st].i))*(long long)p[i]);
    }

    printf("%lld",s);

    return 0;
}