Pagini recente » Cod sursa (job #485487) | Cod sursa (job #2601240) | Cod sursa (job #1833809) | Cod sursa (job #740905) | Cod sursa (job #2891999)
#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;
}