Cod sursa(job #2891956)

Utilizator VladNANegoita Vlad-Andrei VladNA Data 20 aprilie 2022 11:32:54
Problema Secventa 3 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <bits/stdc++.h>
#define NMAX 30005

using namespace std;

const double eps = 0.0001;

int n, l, u;
int c[NMAX], t[NMAX];
int sumc[NMAX], sumt[NMAX];

bool check(double best)
{
	if ((double)sumc[l] / sumt[l] >= best)
		return true;

	deque <int> dq;
	for (int i = 1; i <= l; ++i)
		if ((double)c[i] / t[i] >= best)
			dq.push_back(i);

	for (int i = l + 1; i <= n; ++i) {
		if ((double)c[i] / t[i] >= best)
			dq.push_back(i);

		if (i - dq.front() + 1 > u)
			dq.pop_front();

		while (i - dq.front() + 1 >= l && (double)c[dq.front()] / t[dq.front()] < best)
			dq.pop_front();

		if (i - dq.front() + 1 >= l) {
			if ((double)(sumc[i] - sumc[dq.front() - 1]) / (sumt[i] - sumt[dq.front() - 1]) >= best)
				return true;
		} else {
			if ((double)(sumc[i] - sumc[i - l + 1]) / (sumt[i] - sumt[i - l + 1]) >= best)
				return true;
		}
	}

	return false;
}

int main()
{
	cin >> n >> l >> u;

	for (int i = 1; i <= n; ++i) {
		cin >> c[i];
		sumc[i] = sumc[i - 1] + c[i];
	}

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

	double l = 0, r = sumc[n], mid;
	while (r -l >= eps) {
		mid = (l + r) / 2.0;

		if (check(mid))
			l = mid;
		else
			r = mid;
	}

	cout << setprecision(2) << fixed <<  l;
	return 0;
}