Pagini recente » Cod sursa (job #694977) | Cod sursa (job #2836416) | Cod sursa (job #1817291) | Cod sursa (job #1092374) | Cod sursa (job #2891900)
#include <bits/stdc++.h>
using namespace std;
ifstream in("secv3.in");
ofstream out("secv3.out");
long long n, l, u;
double a[30005], b[30005];
double s[30005];
/// Pot sa verific daca o valoare e mai mare decat costurile tuturor secventelor?
/// (a[1] + a[2] + a[3]) / (b[1] + b[2] + b[3]) < val
/// (a[1] + a[2] + a[3]) < val * (b[1] + b[2] + b[3])
/// (a[1] + a[2] + a[3]) - val * b[1] + val * b[2] + val * b[3]
/// s[0] = 0;
/// s[i] = s[i - 1] + a[i] - val * b[i]
/// s[i] - s[j] < 0 => costul secventei de la indicii j + 1 la i e < val.
/// s[i] - s[j] > 0 => costul ala > val.
/// => Caut daca e o valoare pozitiva s[i] - s[j]
deque<int> q;
bool check(double val)
{
s[0] = 0;
for (int i = 1; i <= n; i++)
s[i] = s[i - 1] + a[i] - val * b[i];
s[n + 1] = s[n];
for (int i = l; i <= n; i++)
{
while (!q.empty() && s[i - l + 1] < s[q.back()])
q.pop_back();
q.push_back(i - l + 1);
if (i - q.front() + 1 > u)
q.pop_front();
if (s[i] - s[q.front()] > 0)
return 1;
}
return 0;
}
int main()
{
in >> n >> l >> u;
for (int i = 1; i <= n; i++)
in >> a[i];
for (int i = 1; i <= n; i++)
in >> b[i];
double down = 0, up = 1000, mid;
for (int i = 0; i <= 50; i++) {
mid = (down + up) / 2;
if (check(mid))
down = mid;
else
up = mid;
}
out << fixed << setprecision(2) << down;
return 0;
}