Cod sursa(job #2891769)

Utilizator matthriscuMatt . matthriscu Data 19 aprilie 2022 19:34:00
Problema Secventa 3 Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <bits/stdc++.h>
using namespace std;

#define name "secv3"
#define NMAX 30005
#define EPS 1e-5

int c[NMAX], t[NMAX], n, l, u;
double v[NMAX];

bool check(double x)
{
	for (int i = 1; i <= n; ++i)
		v[i] = v[i - 1] + c[i] - x * t[i];
	
	deque<int> dq;

	double max_sum = -1;
	for (int i = 1; i <= n; ++i) {
		while (!dq.empty() && dq.front() < i - u)
			dq.pop_front();

		if (!dq.empty() && i >= dq.front() + l)	
			max_sum = max(v[i] - v[dq.front()], max_sum);
			
		while (!dq.empty() && v[dq.back()] >= v[i])
			dq.pop_back();

		dq.push_back(i);
	}

	return max_sum >= 0;
}

int main()
{
	freopen(name ".in", "r", stdin);
	freopen(name ".out", "w", stdout);

	scanf("%d%d%d", &n, &l, &u);

	for (int i = 1, x; i <= n; ++i)
		scanf("%d", &c[i]);

	for (int i = 1; i <= n; ++i)
		scanf("%d", &t[i]);

	double left = 0, right = NMAX;
	while (right - left >= EPS) {
		double mid = (left + right) / 2;
		if (check(mid))
			left = mid;
		else
			right = mid;
	}

	printf("%lf\n", left);
}