Pagini recente » Cod sursa (job #1440740) | Cod sursa (job #1938951) | Cod sursa (job #2229428) | Cod sursa (job #577087) | Cod sursa (job #1289176)
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <deque>
#include <algorithm>
using namespace std;
const int NMAX = 30010;
const double EPS = 1e-3;
int N, L, U, Cost[NMAX], Time[NMAX];
bool CheckOrder(double X, double Y)
{
return X < Y || fabs(X - Y) < EPS;
}
bool Check(double X)
{
double V[NMAX], S[NMAX];
S[0] = 0;
for(int i = 1; i <= N; ++ i)
V[i] = Cost[i] - X * Time[i], S[i] = S[i - 1] + V[i];
deque<int> D;
for(int i = 1; i <= N; ++ i)
{
while(!D.empty() && CheckOrder(S[i], S[D.back()])) D.pop_back();
if(i - L >= 0) D.push_back(i - L);
while(!D.empty() && D.front() < i - U) D.pop_front();
if(!D.empty() && CheckOrder(S[ D.front() ], S[i]))
return 1;
}
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", &Cost[i]);
for(int i = 1; i <= N; ++ i) scanf("%i", &Time[i]);
double Left = 0, Right = 30000, Mid, Ans;
for(int Steps = 0; Steps <= 300; Steps ++)
{
Mid = (Left + Right) / 2;
if(Check(Mid)) Ans = Mid, Left = Mid;
else Right = Mid;
}
printf("%.2lf\n", Ans);
return 0;
}