Cod sursa(job #68689)

Utilizator ViksenVictor-Nicolae Savu Viksen Data 29 iunie 2007 08:04:18
Problema Branza Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.55 kb
#include <stdio.h>
#define baza 1000

struct point { int c,t; } Q[100001];
int cost[100001],S[100],n,s,t,i,j,r,cant,l,re;
long long cost_curent,suma;

//functii pentru structura aia : coada cu doua capete :P
void scufunda ( int cst , int zi )
{
    int cnsm = cst-zi*s;
    for ( ; (r>=l)&&( (cnsm<Q[r].c) || Q[r].c==0 ) ; r-- );
    Q[++r].c=cnsm;Q[r].t=zi;
}


int extrage_cost ( int zi ) //functia asta returneaza costul real.. ca sa nu mai stau sa calculez eu :P
{
 	for ( ; Q[l].t<=zi-t ; l++ );
    return cost[Q[l].t]+(zi-Q[l].t)*s;
}

//procedura recursiva de scriere pentru baza asta mare ;) y=nr exact de cifre;
void scrie ( int x , int y )
{
 	if (y>1) scrie ( x/10 , y-1 );
 	printf ( "%d" , x%10 );
}

//aici are loc actiunea

int main ()
{
 	freopen ( "branza.in" , "r" , stdin );
    scanf ( "%d %d %d" , &n, &s , &t );
    for ( i=0 ; i<n ; i++ ) {
       scanf ( "%d %d" , &cost[i] , &cant );
       scufunda ( cost[i] , i );
	   re = extrage_cost ( i );

       suma += (long long) re * cant;

     /*  for ( j=1 ; cost_curent ; cost_curent/=baza ) {
          cost_curent+=S[j];
          S[j++] = cost_curent%baza;
       }
       S[0]=j-1;
      
       cost_curent = re*cant; */
   //    suma += cost_curent;

      
    }
    fclose ( stdin );
    freopen ( "branza.out" , "w" , stdout );

   // afisam suma

    printf ( "%lld\n" , suma );
   /* printf ( "%d" , S[S[0]] );
    for ( i=S[0]-1 ; i ; i-- )
       scrie ( S[i] , 3 );
    printf ( "\n" ); */
    fclose ( stdout );
    return 0;
}