Cod sursa(job #2891999)

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

using namespace std;

const long double eps = 0.0001;

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

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

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

	deque <int> dq;
	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() > u)
			dq.pop_front();

		if (i - dq.front() >= l && best < sum[i] - sum[dq.front()])
			best = sum[i] - sum[dq.front()];

	}

	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];

	long 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;
}