Cod sursa(job #1737922)

Utilizator valentin50517Vozian Valentin valentin50517 Data 5 august 2016 12:34:39
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.71 kb
#include <bits/stdc++.h>
using namespace std;
int N,C[1<<15],T[1<<15],L,U;
bool check(double d){
	int l=1,r=L,ls=1;
	double c=0,cs=0;
	for(int i=1;i<L;i++) c+=C[i]-T[i]*d; 
	for(;r<=N;r++){
		c+=C[r]-T[r]*d;	
		while(cs >= 0 && r-ls+1>L) cs+=C[ls]-T[ls]*d,ls++;
		if(cs<=0) l=ls,c-=cs,cs=0; 
		while(r-l+1 > L && C[l]-T[l]*d < 0) l++,c-=C[l]-T[l]*d,cs-=(l<ls ? C[l]-T[l]*d : 0);
		if(c >= 0) return true;
	}
	return false;
}
int main(){
	ifstream cin("secv3.in");
	ofstream cout("secv3.out");
	cin >> N >> L >> U;
	for(int i = 1;i<=N;i++) cin >> C[i];
	for(int i = 1;i<=N;i++) cin >> T[i];
	double st=0,dr=1000;
	while(dr-st >= 0.001){
		double mid = (dr+st)/2.0;
		(check(mid) ? st : dr) = mid;
	}
	cout << st;
 	return 0;
}