Cod sursa(job #218865)

Utilizator Pepelea_FlaviuFlaviu Pepelea Pepelea_Flaviu Data 3 noiembrie 2008 20:46:28
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
# include <cstdio>

using namespace std;

# define FIN "branza.in"
# define FOUT "branza.out"
# define min(a,b) (a<b?a:b);
# define MAXN 100010
# define ll long long

ll N,T,S,i,j,f,l,A;
ll Stack[MAXN];
ll LowC[MAXN];
ll C[MAXN];
ll P[MAXN];

    int main()
    {
        freopen(FIN,"r",stdin);
        freopen(FOUT,"w",stdout);
        scanf("%lld%lld%lld",&N,&S,&T);
        for (i=1; i<=N; ++i)
          scanf("%lld%lld",&P[i],&C[i]);
        f=l=1;
        LowC[1]=P[1];
        Stack[1]=1;
        for (i=2; i<=N; ++i)
          {
              A=i-T>1?i-T:1;
              while (Stack[f]<A) f++;
              LowC[i]=min(P[Stack[f]]+(i-Stack[f])*S,P[i]);
              while (P[Stack[l]]+(N-Stack[l])*S>=P[i]+(N-i)*S && l>=f)
                l--;
              Stack[++l]=i;
          }
        A=0;
        for (i=1; i<=N; ++i)
          A+=LowC[i]*C[i];
        printf("%lld",A);
        return 0;
    }