Pagini recente » Cod sursa (job #2101908) | Cod sursa (job #1157426) | Cod sursa (job #1911590) | Cod sursa (job #2739711) | Cod sursa (job #494176)
Cod sursa(job #494176)
#include<cstdio>
#include<algorithm>
#include<set>
const double inf = 100000000.00;
const int maxn = 30005;
using namespace std;
int i , j , v[maxn] , w[maxn] , L, U , n;
double b[maxn] , sum[maxn];
bool possible ( double c ) {
int i , j;
set <double> S;
for( i = 1 ; i <= n ; ++i )
b[i] = v[i] - c * w[i];
for( i = 1 ; i <= n ; ++i )
sum[i] = sum[i - 1] + b[i];
for( i = L ; i <= n ; ++i ) {
S.insert(sum[i - L]);
if ( sum[i] - *S.begin() >= 0 ) return true;
//if ( i >= U ) S.erase(sum[i - U]);
}
return false;
}
double solve() {
double lf , rt , mid , sol = -1, i;
for( lf = 0 , rt = 1024 , i = 1 ; i <= 20 ; ++i ) {
mid = ( lf + rt ) * 0.5;
if ( possible( mid ) ) sol = mid , lf = mid;
else rt = mid;
}
return sol;
}
int main()
{
freopen("secv3.in","r",stdin);
freopen("secv3.out","w",stdout);
scanf("%d %d %d",&n,&L,&U);
for( i = 1 ; i <= n ;++i )
scanf("%d",&v[i]);
for( i = 1 ; i <= n ; ++i)
scanf("%d",&w[i]);
printf("%.3lf",solve());
return 0;
}