Cod sursa(job #357966)

Utilizator tamas_iuliaTamas Iulia tamas_iulia Data 21 octombrie 2009 14:37:47
Problema Branza Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.77 kb
#include <stdio.h>
#define Nmax 100005
#define LL long long

LL n,t,s,p,u,i,rez;
LL deq[Nmax],tmax[Nmax],ind[Nmax];
LL C[Nmax],P[Nmax];
LL m;

int main(){
	freopen("branza.in","r",stdin);
   freopen("branza.out","w",stdout);
   scanf("%lld%lld%lld",&n,&s,&t);
   for(i=1;i<=n;++i) scanf("%lld%lld",&C[i],&P[i]);

   p=1; u=0;
   for(i=1; i<=n; ++i){
   	for(; p<=u && tmax[p] == i; p++);
      ++u;
      deq[u]=C[i] + (n-i) *s;
      tmax[u] = t+i+1;
      ind[u] =i;
      for( ; u>1 && deq[u] < deq[u-1]; u-- ){
      	deq[u-1]=deq[u];
         tmax[u-1]=tmax[u];
         ind[u-1]=ind[u];
      }

      m = ( C[ind[p]] + (i - ind[p])*s ) * P[i];
      rez += m;
   }

   printf("%lld\n",rez);
   fclose(stdin); fclose(stdout);
   return 0;
}