Pagini recente » Cod sursa (job #2609386) | Cod sursa (job #3223986) | Cod sursa (job #2322529) | Cod sursa (job #1989231) | Cod sursa (job #48707)
Cod sursa(job #48707)
#include <cstdio>
#include <deque>
using namespace std;
#define NX 30042
long long t[ NX ], s[ NX ], b[ NX ];
deque< int > Q;
int N, L, U, res;
void cit() {
int i;
long long x;
scanf( "%d%d%d", &N, &L, &U );
for( i = 1; i <= N; i++ ) {
scanf( "%lld", &x );
s[i] = s[i-1] + x;
}
for( i = 1; i <= N; i++ ) {
scanf( "%lld", &x );
t[i] = t[i-1] + x;
}
for( i = 1; i <= N; i++ )
s[i] *= 100;
}
bool pred( int X ) {
int i;
b[0] = 0;
for( i = 1; i <= N; i++ )
b[i] = s[i] - X * t[i];
Q.clear();
for( i = 1; i <= N-L+1; i++ ) {
while( !Q.empty() && Q.front() < i-U+L-1 )
Q.pop_front();
while( !Q.empty() && b[ Q.back() ] > b[ i-1 ] )
Q.pop_back();
Q.push_back( i-1 );
if( b[ i+L-1 ] >= b[ Q.front() ] )
return true;
}
return false;
}
int bs( int lo, int hi ) {
int step, i;
for( step = 1; step < (hi - lo); step <<= 1 );
for( i = lo - 1; step; step >>= 1 )
if( i + step <= hi )
if( pred( i + step ) )
i += step;
return i;
}
void rez() {
res = bs( 1, 100000 );
}
void scr() {
printf( "%d.%02d\n", res / 100, res % 100 );
}
int main() {
freopen( "secv3.in", "r", stdin );
freopen( "secv3.out", "w", stdout );
cit();
rez();
scr();
return 0;
}