Pagini recente » Cod sursa (job #66733) | Cod sursa (job #2472095) | Cod sursa (job #1650580) | Cod sursa (job #409893) | Cod sursa (job #889948)
Cod sursa(job #889948)
#include<cstdio>
#include<deque>
#define MAX 100005
#define nmax 30005
using namespace std;
deque < int > dq;
int n,l,u;
short int c[nmax],t[nmax];
double result;
void read( void )
{
freopen("secv3.in","r",stdin);
scanf("%d%d%d",&n,&l,&u);
for(int i(1); i <= n ; ++i )
scanf("%d",&c[i]);
for(int i(1); i <= n ; ++i )
scanf("%d",&t[i]);
fclose(stdin);
}
bool check ( double m )
{
double s[nmax];
s[0]=0;
dq.clear();
for(int i(1) ; i <= n ; ++i )
s[i]=s[i-1]+(double)c[i]-m*t[i];
for(int i(l) ; i <= n ; ++i )
{
while(!dq.empty() && s[ dq.back() ] >= s[i-l+1])
dq.pop_back();
dq.push_back( i-l+1 );
while( i - dq.front() > u - l )
dq.pop_front();
if( s[i] - s[dq.front()] > 0 )
return true;
}
return false;
}
double solve ( void )
{
double lo=0;
double hi=MAX;
while( hi-lo > 0.0001 )
{
double mid=(hi+lo)/2;
if( check(mid) )
{
result=mid;
lo=mid+0.0001;
}
else
{
hi=mid-0.0001;
}
}
return result;
}
void write( void )
{
freopen("secv3.out","w",stdout);
if(l <= u && l!=u )
printf("%.2lf\n",solve());
fclose(stdout);
}
int main()
{
read();
write();
return 0;
}