Cod sursa(job #2455100)

Utilizator BogdanRazvanBogdan Razvan BogdanRazvan Data 10 septembrie 2019 19:41:54
Problema Secventa 3 Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.33 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 < double > 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];
    double st = 0.0;
    double dr = 1000.0;
    double sol = 0.0;
    while(st <= dr) {
        double mid = (st + dr) / 2;
        dq.clear();
        double sum = 0.0;
        for(int i = 1; i <= n; ++i) {
            while(f[i] >= mid && dq.size() < mx) {
                dq.push_back(f[i]);
                sum += f[i];
                if(dq.size() >= mn) sol = max(sol, 1.0 * sum / dq.size());
                if(dq.size() == mx) {
                    sum -= dq.front();
                    dq.pop_front();
                }
                ++i;
            }
            while(dq.size() > mn) {
                sol = max(sol, 1.0 * sum / dq.size());
                sum -= dq.front();
                dq.pop_front();
            }
        }
        if(sol >= mid) st = mid + 0.01;
        else dr = mid - 0.01;
    }
    fout << fixed << setprecision(2) << sol;
    return 0;
}