Cod sursa(job #68190)

Utilizator crawlerPuni Andrei Paul crawler Data 26 iunie 2007 21:12:54
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.71 kb
#include <cstdio>

using namespace std;

#define Nmax 100100
#define v(r) (c[r] + (n-r)*s)

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

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

        int n,s,t,st,dr;
        long long ret=0;
        st=dr=1;
        c[0] = 2114567890;

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

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

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

        return 0;
}