Cod sursa(job #2431635)

Utilizator mihai50000Mihai-Cristian Popescu mihai50000 Data 20 iunie 2019 14:54:31
Problema Secventa 3 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <bits/stdc++.h>

using namespace std;

ifstream in("secv3.in");
ofstream out("secv3.out");

deque <int> d;

const int DIM = 1e5 + 7;
const int INF = 2e9;

int v[DIM];
int p[DIM];

double c[DIM];

int n, u, l;

bool check(double k)
{
    d.clear();

    for(int i = 1; i <= n; i++)
        c[i] = v[i] * 1.0 - k * p[i] + c[i - 1];

    double mx = c[l];

    int dif = u - l;

    for(int i = l; i <= n; i++)
    {
        while(!d.empty() && c[d.back()] >= c[i - l])
            d.pop_back();

        d.push_back(i - l);

        while(!d.empty() && d.front() + u < i)
            d.pop_front();

        int x = 0;

        if(!d.empty())
            x = d.front();

        mx = max(mx, c[i] - c[x]);
    }

    if(mx >= 0)
        return true;

    return false;
}

int main()
{
    in >> n >> l >> u;

    for(int i = 1; i <= n; i++)
        in >> v[i];

    for(int i = 1; i <= n; i++)
        in >> p[i];

    double st = 0;
    double dr = 100000;

    double ans = 0;

    while(st + 0.001 <= dr)
    {
        double mid = (st + dr) / 2;

        if(check(mid) == true)
        {
            st = mid;
            ans = mid;
        }
        else
        {
            dr = mid;
        }
    }

    out << fixed << setprecision(3) << ans;
}