Cod sursa(job #2891897)

Utilizator LIR16LazarIonutRadu LIR16 Data 20 aprilie 2022 03:41:56
Problema Secventa 3 Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.83 kb
#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]) {
                Max = max(Max, s[i] - s[j]);
                i++;
            }
            else {
                j++;
                if (i - j + 1 < l)
                    i++;
            }
        }
    }

    i = n;
    while (i - j + 1 >= l)
    {
        if (s[i] >= s[j]) {
            Max = max(Max, s[i] - s[j]);
            j++;
        }
    }

    return (Max > 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 <= 40; i++) {
        mid = (down + up) / 2;

        if (check(mid))
            down = mid;
        else
            up = mid;
    }

    out << fixed << setprecision(2) << down;

    return 0;
}