Pagini recente » Cod sursa (job #934312) | Cod sursa (job #2304167) | Cod sursa (job #119405) | Cod sursa (job #2567341) | Cod sursa (job #1471500)
#include <bits/stdc++.h>
using namespace std;
const int INF = 1000000;
const int NM = 30005;
int N,L,U,K;
int C[NM],T[NM];
double Sol;
double Df[NM];
deque< int > D;
bool Check(double X)
{
for (int i = 1;i <= N;i++)
Df[i] = Df[i - 1] + C[i] - (T[i] * X);
D.clear();
for (int i = 0;i <= N - L;i++)
{
while (!D.empty() && Df[D.back()] >= Df[i])
D.pop_back();
D.push_back(i);
//if (i < K) continue;
while (i - D.front() == K)
D.pop_front();
if (Df[i + L] - Df[D.front()] >= 0)
return 1;
}
return 0;
}
int main()
{
freopen("secv3.in","r",stdin);
freopen("secv3.out","w",stdout);
scanf("%d %d %d",&N,&L,&U);
K = U - L + 1;
for (int i = 1;i <= N;i++)
scanf("%d",&C[i]);
for (int i = 1;i <= N;i++)
scanf("%d",&T[i]);
double First = 0,Last = INF;
while(First <= Last)
{
double Middle = (First + Last) / 2.0;
if (Check(Middle))
First = Middle + 0.001;
else
Last = Middle - 0.001;
}
Sol = First - 0.001;
printf("%.3f\n",Sol);
return 0;
}