Pagini recente » Cod sursa (job #1169919) | Cod sursa (job #2583490) | Cod sursa (job #328684) | Cod sursa (job #103294) | Cod sursa (job #1733290)
#include <cstdio>
#include <algorithm>
#include <deque>
#define MaxN 30001
#define INF 2000000000
#define time second
#define value first
#define var 0.001
using namespace std;
pair <int,int> v[MaxN];
int N,U,L;
double S[MaxN]={},lw,hi,mid,Sol;
deque <int>D;
bool Verify(double val)
{
for(int i=1;i<=N;i++)
S[i]=S[i-1]+v[i].value-v[i].time*val;
double Max=-INF;
D.clear();
for(int i=L;i<=N;i++)
{
while(!D.empty()&&S[D.back()]>=S[i-L])
D.pop_back();
D.push_back(i-L);
while(D.front()<=i-U)
D.pop_front();
if(Max<S[i]-S[D.front()])
Max=S[i]-S[D.front()];
}
if(Max>=0)
return true;
else return false;
}
int main()
{
freopen("secv3.in","r",stdin);
freopen("secv3.out","w",stdout);
scanf("%d%d%d",&N,&L,&U);
v[0].value=v[0].time=0;
for(int i=1;i<=N;i++)
scanf("%d",&v[i].value);
for(int i=1;i<=N;i++)
scanf("%d",&v[i].time);
lw=0,hi=1001,mid;
while(lw<=hi)
{
mid=(lw+hi)/2;
if(Verify(mid))
{
Sol=mid;
lw=mid+var;
}
else hi=mid-var;
}
printf("%lf",Sol);
return 0;
}