Pagini recente » Cod sursa (job #2783963) | Cod sursa (job #1942316) | Cod sursa (job #880919) | Cod sursa (job #575029) | Cod sursa (job #997585)
Cod sursa(job #997585)
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <deque>
#include <algorithm>
using namespace std;
const int NMAX = 30005;
const double EPS = 1e-7;
int N, L, U, C[NMAX], T[NMAX];
double V[NMAX], S[NMAX];
deque<int> D;
int Check(double M)
{
for(int i = 1; i <= N; ++ i)
{
V[i] = C[i] - M * T[i];
S[i] = S[i - 1] + V[i];
}
D.clear();
for(int i = L; i <= N; ++ i)
{
while(!D.empty() && S[i - L] < S[D.back()]) D.pop_back();
D.push_back(i - L);
while(!D.empty() && D.front() < i - U) D.pop_front();
if(!D.empty() && S[i] >= S[D.front()]) return i;
}
return 0;
}
int main()
{
freopen("secv3.in", "r", stdin);
freopen("secv3.out", "w", stdout);
scanf("%i %i %i", &N, &L, &U);
for(int i = 1; i <= N; ++ i)
scanf("%i", &C[i]);
for(int i = 1; i <= N; ++ i)
scanf("%i", &T[i]);
double Left = 0.0, Right = 1000.0, Mid, Ans;
while(fabs(Right - Left) > EPS)
{
Mid = (Left + Right) / 2;
if(Check(Mid)) Ans = Mid, Left = Mid;
else Right = Mid;
}
printf("%.2f\n", Ans);
return 0;
}