Cod sursa(job #67483)

Utilizator crawlerPuni Andrei Paul crawler Data 25 iunie 2007 09:58:55
Problema Branza Scor 0
Compilator cpp Status done
Runda preONI 2007, Runda Finala, Clasa a 10-a Marime 0.79 kb
#include <cstdio>

using namespace std;

#define Nmax 100100

int c[Nmax], p[Nmax], w[Nmax], v[Nmax];

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

        int n,s,t;

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

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

        int st,dr, ret=0;
        st=dr=1;
        v[0] = 2114567890;

        for (int i=1;i<=n;++i)
        {
                while(v[w[dr]] > v[i] && st<=dr)
                        --dr;
                w[++dr] = i;
                ret += (v[w[st]] - (n-i)*s)*p[i];
                if(w[st] == i-t) ++st;                
        }

        printf("%d\n", ret);

        return 0;
}