Cod sursa(job #335011)

Utilizator DraStiKDragos Oprica DraStiK Data 28 iulie 2009 13:29:02
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 kb
#include <stdio.h>
#define DIM 100005

int c[DIM],p[DIM],m[DIM],dq[DIM];
long long nrt;
int n,s,t;

void read ()
{
    int i;

    scanf ("%d%d%d",&n,&s,&t);
    for (i=1; i<=n; ++i)
        scanf ("%d%d",&c[i],&p[i]);
}

void solve ()
{
    int i,st,dr;

    for (i=st=1, dr=0; i<=n; ++i)
    {
        for ( ;st<=dr && c[i]+(n-i)*s<c[dq[dr]]+(n-dq[dr])*s; --dr);
        dq[++dr]=i;
		m[i]=c[dq[st]]+(i-dq[st])*s;
        if (dq[st]==i-t)
            ++st;
    }
}

void print ()
{
    int i;

    for (i=1; i<=n; ++i)
        nrt+=(long long)m[i]*p[i];
    printf ("%lld",nrt);
}

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

    read ();
    solve ();
    print ();

    return 0;
}