Pagini recente » Cod sursa (job #1108670) | Cod sursa (job #2438817) | Cod sursa (job #36074) | Cod sursa (job #137026) | Cod sursa (job #2891899)
#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 cea mai mare dif pozitiva s[i] - s[j]
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];
int j = 0, i = l;
double Max = -9999;
while(i - j + 1 <= u && s[i] < s[j] && i <= n)
i++;
while (i <= n)
{
if (i - j + 1 > u)
j++;
else {
if (s[i] > s[j]) {
return 1;
}
else {
j++;
if (i - j + 1 < l)
i++;
}
}
}
i = n;
while (i - j + 1 >= l)
{
if (s[i] > s[j]) {
return 1;
j++;
}
}
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;
}