Pagini recente » Cod sursa (job #2613484) | Cod sursa (job #1038406) | Cod sursa (job #2657625) | Cod sursa (job #2394095) | Cod sursa (job #1254237)
#include <deque>
#include <fstream>
#include <iomanip>
using namespace std;
ifstream fin("secv3.in");
ofstream fout("secv3.out");
const double dif= 0.001;
const int inf= (1<<30)-1+(1<<30);
const int nmax= 30000;
const int out_precision= 2;
double sol;
double a[nmax+1], b[nmax+1], spc[nmax+1];
int n, u, l;
int check( double x ) {
for ( int i= 1; i<=n; ++i ) {
spc[i]= spc[i-1]+a[i]-x*b[i];
}deque <int> d;
for ( int i= l; i<=n; ++i ) {
for ( ; !d.empty() && spc[i-l]<=spc[d.back()]; d.pop_back() ) ;
d.push_back(i-l);
if ( d.front()==i-u-1 ) d.pop_front();
if ( spc[i]>spc[d.front()] ) {
return 1;
}
}
return 0;
}
int main( ) {
fin>>n>>l>>u;
for ( int i= 1; i<=n; ++i ) {
fin>>a[i];
}
for ( int i= 1; i<=n; ++i ) {
fin>>b[i];
}
double left= 0, right= inf, mid;
while ( left<=right ) {
mid= ((double)left+right)/2;
if ( check(mid) ) {
sol= mid;
left= mid+dif;
} else {
right= mid-dif;
}
}
fout<<setprecision(out_precision)<<fixed;
fout<<sol<<"\n";
return 0;
}