Pagini recente » Cod sursa (job #3234649) | Cod sursa (job #183110) | Cod sursa (job #1677911) | Cod sursa (job #1431209) | Cod sursa (job #2905185)
#include <fstream>
#include <iomanip>
#include <deque>
using namespace std;
const int MAX_N = 3 * 1e4;
int a[MAX_N + 1], t[MAX_N + 1];
double tmp[MAX_N + 1];
int n, l, u;
bool ok(double x) {
deque<int> dq;
tmp[0] = 0;
for (int i = 1; i <= n; i++) {
tmp[i] = tmp[i - 1] + a[i] - x * t[i];
if (i >= l) {
if (!dq.empty() && dq.front() == i - u + 1) {
dq.pop_front();
}
while (!dq.empty() && tmp[i - l] <= tmp[dq.back()]) {
dq.pop_back();
}
dq.push_back(i - l);
if (tmp[i] - tmp[dq.front()] >= 0) {
return true;
}
}
}
return false;
}
double cb() {
double st = 0, dr = (1 << 20), sol = 0;
for (int pas = 1; pas <= 100; pas++) {
double mijl = (st + dr) / 2;
if (ok(mijl)) {
sol = mijl;
st = mijl;
} else {
dr = mijl;
}
}
return sol;
}
int main() {
ifstream fin("secv3.in");
ofstream fout("secv3.out");
fin >> n >> l >> u;
for (int i = 1; i <= n; i++) {
fin >> a[i];
}
for (int i = 1; i <= n; i++) {
fin >> t[i];
}
double answer = cb();
fout << setprecision(2) << fixed << answer;
return 0;
}