Cod sursa(job #852634)

Utilizator BarracudaFMI-Alex Dobrin Barracuda Data 11 ianuarie 2013 15:26:01
Problema Secventa 3 Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include<fstream>
#include<deque>
#define MAX 1000
using namespace std;

int c[30001],t[30001];
int i,n,l,u;
double st,dr,med,m,medie;
ifstream f("secv3.in");
ofstream g("secv3.out");
int check (double  med) {
	double x[n+1];
	double y[n+1];
	x[0]=0;
	int i;
	for(i=1;i<=n;++i)
		x[i]=x[i-1]+(double)c[i]-med*t[i];
	
	deque<int>q;
	
	for(i=1;i<=n;++i){
		
		while(!q.empty() && x[q.back()]<=x[i])
			q.pop_back();
		
		q.push_back(i);
		while(i-q.front()>u-l)
			q.pop_front();
		y[i]=x[i]-x[q.front()];
		
	}
	for(i=l;i<=n;++i){
		if(x[i]-x[i-l]+y[i-l]>=0)
			return 1;
	}
	return 0;
}
int main () {
	f>>n>>l>>u;
	
	for(i=1;i<=n;++i)
		f>>c[i];
	for(i=1;i<=n;++i)
		f>>t[i];
	st=0;
	dr=MAX;
	while(st<=dr) {
		
		m=(st+dr)/2;
		if(check(m)){
			medie=m;
			st=m+0.001;
		}
		else
			dr=m-0.001;
	}
	g<<medie<<"\n";
	return 0;
}