Cod sursa(job #2891899)

Utilizator LIR16LazarIonutRadu LIR16 Data 20 aprilie 2022 03:44:44
Problema Secventa 3 Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.76 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]) {
                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;
}