Cod sursa(job #216723)

Utilizator zombie_testertest test zombie_tester Data 25 octombrie 2008 14:52:21
Problema Branza Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 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

long long N,T,S,i,j,f,l,A;
long long Stack[MAXN];
long long LowC[MAXN];
long long C[MAXN];    // cantitate
long long P[MAXN];    // pret

    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 = 1; l = 0;
        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(LowC[Stack[f]] + (i-Stack[f])*S,P[i]);
              while (LowC[Stack[l]]+(N-Stack[l])*S>=LowC[i]+(N-i)*S && l>=f)
                l--;
              Stack[++l] = i;
          }
        
        A = 0;
        for (i = 1; i <= N; ++i)
          A += C[i] * LowC[i];
          
        printf("%lld",A);
        
        return 0;
    }