Cod sursa(job #2892038)

Utilizator VladNANegoita Vlad-Andrei VladNA Data 20 aprilie 2022 15:59:21
Problema Secventa 3 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <bits/stdc++.h>
#define NMAX 30005
#define INF 30000005

using namespace std;

const double eps = 0.000001;

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

/*
 * subsequence of maximum sum
 * with minimum l and maximum u elements
 */
double compute()
{
	double best = -INF;

	for (int i = l; i <= u; ++i)
		best = max(best, sum[i]);

	deque <int> dq;

	int length = u - l + 1;
	for (int i = 1; i <= n; ++i) {
		while (!dq.empty() && sum[dq.back()] >= sum[i])
			dq.pop_back();

		dq.push_back(i);

		while (i - dq.front() + 1 >= length)
			dq.pop_front();

		minimum[i] = dq.front();///indexul elementului minimumim din secventa i - length + 1 ... i
	}

	for (int i = l + 1; i <= n; ++i) {
		best = max(best, sum[i] - sum[minimum[i - l]]);
	}
	return best;
}

bool check(double best)
{
	sum[0] = 0.0;
	for (int i = 1; i <= n; ++i)
		sum[i] = sum[i - 1] + c[i] - best * t[i];

	if (compute() >= 0)
		return true;

	return false;
}

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

	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 left = 0, right = INF, mid;
	while (right - left >= eps) {
		mid = (left + right) / 2.0;

		if (check(mid))
			left = mid;
		else
			right = mid;
	}

	cout <<  left << '\n';
	return 0;
}