Cod sursa(job #95558)

Utilizator znakeuJurba Andrei znakeu Data 29 octombrie 2007 14:36:50
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <stdio.h>
#include <deque.h>
int c[100001],p[100001],m[100001];


int main()
{
	int n,s,t,i,min1=0,elem,st,j;
	deque<int> Q;
	
	FILE *in  = fopen("branza.in","r");
	FILE *out = fopen("branza.out","w");
	
	fscanf(in,"%d%d%d",&n,&s,&t);
	
	for (i=0; i<n; i++)
		fscanf(in,"%d%d",&c[i],&p[i]);
	
	m[0]=c[0];
	min1=0;
	Q.push_back(c[0]);
	elem=1;
	
	for (i=1 ;i<n; i++)
	{
		if(elem<t)
		{
			Q.push_back(c[i]);
			if (c[i]<Q[min1]+s*(i-min1) )
			{
				min1=i;
				m[i]=c[i];
			}
			else
			{
				m[i]=Q[min1]+s*(i-min1);
			}
			elem++;
		}
		else
		{
			Q.push_back(c[i]);
			Q.pop_front();
			min1--;
			if (min1<0)
			{
				min1=0;
				for (j=1; j<elem; j++)
					if (Q[j]<Q[min1]+s*(j-min1) )
					{
						min1=j;
					}
			}
			else
			{
				if (c[i]<Q[min1]+s*(elem-min1-1) )
				{
					min1=elem-1;
					m[i]=c[i];
				}
				else
				{
					m[i]=Q[min1]+s*(elem-min1-1);
				}				
			}
		}
	}
	
	st=0;
	for (i=0; i<n; i++)
	{
		st+=p[i]*m[i];
	}
	
	fprintf(out,"%d\n",st);
	
	fclose(in);
	fclose(out);	
	
	return 0;
}