Cod sursa(job #306175)

Utilizator DraStiKDragos Oprica DraStiK Data 19 aprilie 2009 22:15:21
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.73 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+=m[i]*p[i];
    printf ("%lld",nrt);
}
int main ()
{
    freopen ("branza.in","r",stdin);
    freopen ("branza.out","w",stdout);
    read ();
    solve ();
    print ();
    return 0;
}