Pagini recente » Cod sursa (job #1757800) | Cod sursa (job #2645836) | Cod sursa (job #2577981) | Cod sursa (job #2387176) | Cod sursa (job #1257059)
#include<fstream>
#include<deque>
using namespace std;
ifstream fin( "secv3.in" );
ofstream fout( "secv3.out" );
const int nmax = 30000;
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() {
int m;
fin >> n >> l >> u;
for( int i = 1; i <= n; ++ i ) {
fin >> a[ i ];
}
for( int i = 1; i <= n; ++ i ) {
fin >> b[ i ];
}
m = 0;
for( int step = 1 << 30; step > 0; step >>= 1 ) {
if ( check( (double)(m + step) / 100 ) ) {
m += step;
}
}
fout << (double)m / 100 << "\n";
fin.close();
fout.close();
return 0;
}