Pagini recente » Cod sursa (job #2923069) | Cod sursa (job #690724) | Cod sursa (job #2855547) | Cod sursa (job #325941) | Cod sursa (job #1458128)
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
const int SHIFT = 100;
int n , L , R , i;
vector < int > x , y;
vector < long long > dp;
deque < int > dq;
bool check(int val)
{
/// Sx / Sy = val => Sx - val * Sy = 0 => daca Sx - val * Sy >= 0 - exista solutia val
int i; dq.clear();
for (i = 1; i <= n; ++i)
dp[i] = dp[i-1] + x[i] * SHIFT - y[i] * val;
for (i = L; i <= n; ++i)
{
while (dq.size() && dp[dq.back()] >= dp[i-L])
dq.pop_back();
dq.push_back(i-L);
if (i - dq.front() > R)
dq.pop_front();
if ((dp[i] - dp[dq.front()]) >= 0)
return 1;
}
return 0;
}
float Binary_Search()
{
int i , step , N = 1000 * SHIFT;
for (step = 1; step < N; step <<= 1);
for (i = 0; step; step >>= 1)
if (i + step <= N && check(i + step))
i += step;
return 1.0 * i / SHIFT;
}
int main()
{
freopen("secv3.in","r",stdin);
freopen("secv3.out","w",stdout);
scanf("%d %d %d", &n, &L, &R);
x = vector < int > (n + 1); y = vector < int > (n + 1); dp = vector < long long > (n + 1);
for (i = 1; i <= n; ++i)
scanf("%d", &x[i]);
for (i = 1; i <= n; ++i)
scanf("%d", &y[i]);
printf("%.2f", Binary_Search());
return 0;
}