Pagini recente » Cod sursa (job #2242155) | Cod sursa (job #1265943) | Cod sursa (job #303977) | Cod sursa (job #604885) | Cod sursa (job #889944)
Cod sursa(job #889944)
#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;
}
void 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;
}
}
}
void write( void )
{
freopen("secv3.out","w",stdout);
printf("%.2lf\n",result);
fclose(stdout);
}
int main()
{
read();
if(l!=u)
solve();
write();
return 0;
}