Cod sursa(job #878715)

Utilizator MirceaD85Mircea Digulescu MirceaD85 Data 14 februarie 2013 18:31:28
Problema Secventa 3 Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.55 kb
#include <iostream>
#include <fstream>

using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */

#define MAX 32020

int cost[MAX];
int timp[MAX];

double C[MAX];
double T[MAX];

int n, l, u;

ifstream in("secv3.in");
ofstream out("secv3.out");

int st, ed;
int stack[MAX];

double rez;

double cst(int i)
{
	return C[i]/rez-T[i];
}

void insert(int x)
{
	if(ed = -1)
	 {
	 	stack[0]=x;
	 	st=ed=0;
	 	return;
	 }
	
	ed++;
	stack[ed]=x;
	
	while(ed>0 && ed!=st)
	if(cst(stack[ed]) < cst(stack[ed-1]))
	  {
	  	stack[ed-1]=stack[ed];
	  	ed--;
	  }
}

int top()
{
	return stack[ed];
}

int bottom()
{
	if(ed==-1)
	 return -1;
	 
	return stack[st];
}

void discardbottom()
{
	st++;
}

void clear()
{
  ed = -1;
}

int size()
{
	return ed-st+1;
}

int main() {
	in>>n>>l>>u;
	int i;
	double arez=1.0/1000, brez=1000.0;
	for(i=1;i<=n;i++)
	 in>>cost[i];
	for(i=1;i<=n;i++)
	 in>>timp[i];
	
	T[0]=timp[0];
	for(i=1;i<=n;i++)
	 T[i]=T[i-1]+timp[i];
	for(i=1;i<=n;i++)
	 C[i]=C[i-1]+cost[i];
	 
	rez=(brez+arez)/2;
	while((brez-arez)>0.01)
	{
		rez = (brez+arez)/2;
		
		clear();
		insert(0);

		int i=1;
		int j;
		for(j=l;j<=n;j++)
		 {
		 	int k = bottom();
		 	if(cst(j) >= cst(k))
		 	{ // it is viable
				arez = rez;
				break;
		 	}
		 	
		 	insert(i);
		 	i++;
		 	if(size()>u-l)
		 	  discardbottom();
		 }
		 if(j>n)
		   brez = rez;
	}
	rez =(brez+arez)/2.0; 
	out<<rez<<"\n";
	
	return 0;
}