Cod sursa(job #2031612)

Utilizator eragon0502Dumitrescu Dragos eragon0502 Data 3 octombrie 2017 16:39:15
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 kb
#include <cstdio>

using namespace std;

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

long long c[100005];
long long p[100005];

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

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

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

    for(int i=1;i<=n;++i)
    {
        scanf("%lld %lld",&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;
}