Pagini recente » Monitorul de evaluare | Cod sursa (job #1925969) | Cod sursa (job #808119) | Profil Vlad_Souca | Cod sursa (job #793614)
Cod sursa(job #793614)
#include <cstdio>
#include <cstdlib>
#include <deque>
using namespace std;
#define eps 0.01
#define nmax 30010
#define pf push_front
#define pb push_back
#define ppb pop_back
#define ppf pop_front
int A[nmax], B[nmax], N, L, U;
double S[nmax];
bool Check(double mid)
{
int i;
deque<int> D;
for(S[0] = 0, i = 1; i <= N; i++)
S[i] = S[i - 1] + 1.0 * A[i] - mid * B[i];
D.pf(0);
for(i = L; i <= N; i++)
{
while(!D.empty() && S[i - L] < S[D.back()])
D.ppb();
D.pb(i - L);
if(D.front() == i - U - 1) D.ppf();
if(S[i] >= S[D.front()]) return true;
}
return false;
}
double BS()
{
double ans, left = 0, right = 1000, mid;
while(left < right)
{
mid = (left + right) / 2;
if(Check(mid))
ans = mid, left = mid + eps;
else
right = mid - eps;
}
return ans;
}
int main()
{
freopen("secv3.in", "r", stdin);
freopen("secv3.out", "w", stdout);
int i;
scanf("%i %i %i", &N, &L, &U);
for(i = 1; i <= N; i++)
scanf("%i", &A[i]);
for(i = 1; i <= N; i++)
scanf("%i", &B[i]);
printf("%.2lf\n", BS());
return 0;
}