Cod sursa(job #2455158)

Utilizator BogdanRazvanBogdan Razvan BogdanRazvan Data 10 septembrie 2019 21:02:57
Problema Secventa 3 Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <bits/stdc++.h>

using namespace std;


ifstream fin ("secv3.in");
ofstream fout ("secv3.out");
int c[30005], t[30005];
double f[30005];

deque < int > dq;
int main()
{
    ios::sync_with_stdio(false);
    fin.tie(0);

    int n, mn, mx;
    fin >> n >> mn >> mx;
    for(int i = 1; i <= n; ++i) fin >> c[i];
    for(int i = 1; i <= n; ++i) fin >> t[i];
    for(int i = 1; i <= n; ++i) f[i] = 1.0 * c[i] / t[i];
    for(int i = 2; i <= n; ++i) c[i] = c[i - 1] + c[i], t[i] = t[i - 1] + t[i];
    double st = 0.0;
    double dr = 1000.0;
    double sol = 0.0;
    while(st <= dr) {
        double mid = (st + dr) / 2;
        dq.clear();
        for(int i = 1; i <= n; ++i) {
            while(f[i] >= mid && dq.size() < mx) {
                dq.push_back(i);
                if(dq.size() >= mn) sol = max(sol, 1.0 * (c[i] - c[dq.front() - 1]) / (t[i] - t[dq.front() - 1]));
                if(dq.size() == mx)
                    dq.pop_front();
                ++i;
            }
            while(dq.size() > mn) {
                sol = max(sol, 1.0 * (c[i] - c[dq.front() - 1]) / (t[i] - t[dq.front() - 1]));
                dq.pop_front();
            }
            dq.clear();
        }
        if(sol >= mid) st = mid + 0.01;
        else dr = mid - 0.01;
    }
    fout << fixed << setprecision(10) << sol;
    return 0;
}