Pagini recente » Cod sursa (job #2490778) | Cod sursa (job #3306458) | Cod sursa (job #3258359) | Cod sursa (job #728617) | Cod sursa (job #3320192)
#include <bits/stdc++.h>
#define ld double
using namespace std;
ifstream fin("secv3.in");
ofstream fout("secv3.out");
const int NMAX = 3e4;
int n, l, u;
int a[NMAX + 1];
int b[NMAX + 1];
int sp_a[NMAX + 1];
int sp_b[NMAX + 1];
ld get_value(int i, ld x) {
return sp_a[i] - x * sp_b[i];
}
bool check(ld x) {
deque<int> dq;
for(int i = l; i <= n; i++) {
while(!dq.empty() && dq.front() < i - u + 1) {
dq.pop_front();
}
ld value_here = get_value(i - l, x);
while(!dq.empty() && get_value(dq.back() - 1, x) >= value_here) {
dq.pop_back();
}
dq.push_back(i - l + 1);
if(get_value(i, x) >= get_value(dq.front() - 1, x)) {
return true;
}
}
return false;
}
int main() {
fin >> n >> l >> u;
for(int i = 1; i <= n; i++) {
fin >> a[i];
}
for(int i = 1; i <= n; i++) {
fin >> b[i];
}
for(int i = 1; i <= n; i++) {
sp_a[i] = sp_a[i - 1] + a[i];
sp_b[i] = sp_b[i - 1] + b[i];
}
ld left = 0, right = 1e9;
int iter = 100;
while(iter--) {
ld mid = (left + right) / 2;
if(check(mid)) {
left = mid;
}
else {
right = mid;
}
}
fout << fixed << setprecision(2) << left << '\n';
return 0;
}