Pagini recente » Cod sursa (job #2895543) | Cod sursa (job #2125965) | Cod sursa (job #2280237) | Cod sursa (job #2285169) | Cod sursa (job #2892038)
#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;
}