Cod sursa(job #2094327)

Utilizator TudoseSanzianaTudose Sanziana TudoseSanziana Data 25 decembrie 2017 18:07:27
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <bits/stdc++.h>
using namespace std;

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

const int NMAX = 30000, EPS = 0.001;
const double CMAX = 1000;

int n, l, u;
int c[NMAX + 2], t[NMAX + 2];

double ans;
double tmp[NMAX + 2];

bool check(double arg)
{
    deque<int> dq;

    for(int i = 1; i <= n; i++)
    {
        tmp[i] = c[i] - arg * t[i];
        tmp[i] += tmp[i - 1];
    }

    for(int i = l; i <= n; i++)
    {
        while(!dq.empty() && dq.front() <= i - u)
            dq.pop_front();
        while(!dq.empty() && tmp[dq.back()] >= tmp[i - l])
            dq.pop_back();

        dq.push_back(i - l);

        if(tmp[i] - tmp[dq.front()] >= EPS)
            return true;
    }

    return false;
}

int main()
{
    in >> n >> l >> u;
    for(int i = 1; i <= n; i++)
        in >> c[i];
    for(int i = 1; i <= n; i++)
        in >> t[i];

    double st = 0, dr = CMAX, med;
    while(st <= dr)
    {
        med = (st + dr) / 2;
        if(check(med))
        {
            ans = med;
            st = med + 0.001;
        }
        else dr = med - 0.001;
    }

    out << setprecision(2) << fixed << ans << '\n';

    return 0;
}