Pagini recente » Cod sursa (job #2572417) | Cod sursa (job #1512408) | Cod sursa (job #2259982) | Cod sursa (job #2837349) | Cod sursa (job #2094633)
#include <fstream>
#include <deque>
#include <iomanip>
#include <cmath>
using namespace std;
ifstream fin ("secv3.in"); ofstream fout ("secv3.out");
const int nmax = 3e4;
const double eps = 1e-3;
int n, l, u;
int a[nmax + 1], b[nmax + 1];
double v[nmax + 1];
deque< int > d;
bool check (double val) {
for (int i = 0; i <= n; ++ i) {
v[ i ] = (double)a[ i ] - val * b[ i ];
}
d.clear();
for (int i = l; i <= n; ++ i) {
while (!d.empty() && v[ d.back() ] >= v[i - l]) {
d.pop_back();
}
d.push_back(i - l);
if (d.front() < i - u) {
d.pop_front();
}
if (v[ i ] >= v[ d.front() ]) {
return 1;
}
}
return 0;
}
int main () {
fin >> n >> l >> u;
for (int i = 1; i <= n; ++ i) {
int x;
fin >> x;
a[ i ] = a[i - 1] + x;
}
for (int i = 1; i <= n; ++ i) {
int x;
fin >> x;
b[ i ] = b[i - 1] + x;
}
double x, y;
x = 1 / 3e7; y = 3e7;
while (fabs(x - y) >= eps) {
double mij = (x + y) / 2;
if (check( mij )) {
x = mij;
} else {
y = mij;
}
}
fout << setprecision( 5 ) << fixed;
fout << x << "\n";
fin.close();
fout.close();
return 0;
}