Pagini recente » Cod sursa (job #1287838) | Cod sursa (job #1714447) | Cod sursa (job #1098966) | Cod sursa (job #112664) | Cod sursa (job #1260464)
#include<fstream>
#include<deque>
#include<iomanip>
using namespace std;
ifstream fin( "secv3.in" );
ofstream fout( "secv3.out" );
const int nmax = 30000;
const double eps = 0.001;
const int inf = 1 << 30;
int n, u, l;
double a[ nmax + 1 ], b[ nmax + 1 ], c[ nmax + 1 ];
deque <int> d;
bool check( double x ) {
d.clear();
for( int i = 1; i <= n; ++ i ) {
c[ i ] = c[ i - 1 ] + a[ i ] - x * b[ i ];
}
for( int i = 1; i <= n - l; ++ i ) {
while ( !d.empty() && c[ d.back() ] > c[ i ] ) {
d.pop_back();
}
d.push_back( i );
if ( d.front() < i - u + l ) {
d.pop_front();
}
if ( i - u + l > 0 ) {
if ( c[ i + l ] > c[ d.front() ] ) {
return 1;
}
}
}
return 0;
}
int main() {
double st, dr, mid;
fin >> n >> l >> u;
for( int i = 1; i <= n; ++ i ) {
fin >> a[ i ];
}
for( int i = 1; i <= n; ++ i ) {
fin >> b[ i ];
}
st = 0; dr = inf;
while ( st <= dr ) {
mid = (st + dr) / 2;
if ( check( mid ) ) {
st = mid + eps;
} else {
dr = mid - eps;
}
}
fout << setprecision( 3 ) << fixed;
fout << mid << "\n";
fin.close();
fout.close();
return 0;
}