Cod sursa(job #2217143)

Utilizator Dobricean_IoanDobricean Ionut Dobricean_Ioan Data 29 iunie 2018 12:29:18
Problema Secventa 3 Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <deque>
#include <fstream>
#include <iomanip>

using namespace std;

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

const int Dim = 30001;

int n,l,u;
double Sum[Dim],sol;
pair < double , double > A[Dim];
deque < int > D;
void CB();

int main() {
	
	fin >> n >> l >> u;
	for ( int i = 1; i <= n; ++i)
		fin >> A[i].first;
	for ( int i = 1; i <= n; ++i)
		fin >> A[i].second;
	CB();
	fout << fixed << setprecision(2) << sol;
}

bool Ok ( double value) {
	for ( int i = 1; i <= n; ++i)
		Sum[i] = Sum[i-1] +  (double)A[i].first -value * A[i].second;
	D.clear();
	for ( int i = 1; i <= n; ++i) {
		while ( !D.empty() and Sum[i - 1] <= Sum[D.back()])
			D.pop_back();
		D.push_back(i-1);
		if ( i >= u and !D.empty() and D.front() <= i - u)
			D.pop_front();
		if (!D.empty() and  Sum[i] - Sum[D.front()] >= 0  )
			return true;
	}
	return false;
}

void CB() {
	
	double st = 1, dr = 100000,mj;
	while( st <= dr) {
		mj = (st + dr) / 2;
		if( Ok((double) mj/ 100) ) {
			st = mj + 1;
			sol = (double) mj / 100;
		}
		else
			dr = mj - 1;
	}
}