Cod sursa(job #3185013)

Utilizator livliviLivia Magureanu livlivi Data 17 decembrie 2023 16:54:47
Problema Secventa 3 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.42 kb
/*
cb x (ans):

(c[i] - c[j]) / (t[i] - t[j]) >= x
<=> (c[i] - t[i] * x) - (c[j] - t[j] * x) >= 0
<=> max(d[i] - d[j]) >= 0 cu i - u <= j <= i - l
*/

#include <fstream>
#include <iomanip>
#include <vector>
#include <deque>

using namespace std;

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

double get_max_lin(double x, vector<double>& c, vector<double>& t, int l, int u) {
	int n = c.size() - 1;
	vector<double> d(n + 1);
	for (int i = 1; i <= n; i++) {
		d[i] = c[i] - x * t[i];
	}

	double ans = d[l];
	deque<pair<double, int>> stk;
	for (int i = l; i <= n; i++) {
		while (!stk.empty() && stk.back().first > d[i - l]) {
			stk.pop_back();
		}
		stk.push_back({d[i - l], i - l});
		
		ans = max(ans, d[i] - stk.front().first);

		if (stk.front().second == i - u) {
			stk.pop_front();
		}
	}

	return ans;
}

double cb(vector<double>& c, vector<double>& t, int l, int u) {
	double st = 0;
	double dr = 3e7;

	for (int i = 0; i < 100; i++) {
		double mid = (st + dr) / 2;
		if (get_max_lin(mid, c, t, l, u) >= 0) {
			st = mid;
		} else {
			dr = mid;
		}
	}

	return (st + dr) / 2;
}

void Solve() {
	int n; cin >> n;
	int l, u; cin >> l >> u;
	
	vector<double> c(n + 1);
	for (int i = 1; i <= n; i++) {
		cin >> c[i];
		c[i] += c[i - 1];
	}

	vector<double> t(n + 1);
	for (int i = 1; i <= n; i++) {
		cin >> t[i];
		t[i] += t[i - 1];
	}

	cout << fixed << setprecision(3) << cb(c, t, l, u) << "\n";
}

int main() {
	Solve();
	return 0;
}