Pagini recente » Clasament buzdugan_caut_maner | Viata de dupa olimpiade? (partea I) | Cod sursa (job #2809982) | Autentificare | Cod sursa (job #2809974)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb push_back
const string filename = "secv3";
ifstream fin(filename + ".in");
ofstream fout(filename + ".out");
const double err = 0.0001;
int n, l, r;
int a[30005], b[30005];
double c[30005];
deque<int> d;
bool ok(double x)
{
d.clear();
for (int i = 1; i <= n; ++i)
c[i] = c[i - 1] + a[i] - x * b[i];
for (int i = l; i <= n; ++i)
{
if(!d.empty() && i - d.front() + 1 > r)
d.pop_front();
while (!d.empty() && c[d.back()] >= c[i - l])
d.pop_back();
d.push_back(i - l);
if (c[i] - c[d.front()] >= 0.0)
return true;
}
return false;
}
int main() {
fin >> n >> l >> r;
for (int i = 1; i <= n; ++i)
fin >> a[i];
for (int i = 1; i <= n; ++i)
fin >> b[i];
double st = 0.0, dr = 2000.0, ans = 0;
while (dr - st >= err)
{
double mid = (st + dr) / 2.0;
if (ok(mid)) {
ans = mid;
st = mid;
}
else dr = mid;
}
fout << fixed << setprecision(2) << ans << '\n';
fin.close();
fout.close();
return 0;
}