Cod sursa(job #67592)

Utilizator ViksenVictor-Nicolae Savu Viksen Data 25 iunie 2007 12:21:27
Problema Branza Scor 0
Compilator cpp Status done
Runda preONI 2007, Runda Finala, Clasa a 10-a Marime 1.29 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,suma,cant,l,re;
long long cost_curent;

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 )
{
 	for ( ; Q[l].t<zi-t ; l++ );
    return cost[Q[l].t]+(zi-Q[l].t)*s;
}

void scrie ( int x , int y )
{
 	if (y>1) scrie ( x/10 , y-1 );
 	printf ( "%d" , x%10 );
}

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 );

       cost_curent = (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 );
   // printf ( "%d" , suma );
    printf ( "%d" , S[S[0]] );
    for ( i=S[0]-1 ; i ; i-- )
       scrie ( S[i] , 3 );
    printf ( "\n" );
    fclose ( stdout );
    return 0;
}