Cod sursa(job #2328223)

Utilizator andreisontea01Andrei Sontea andreisontea01 Data 25 ianuarie 2019 15:28:51
Problema Secventa 3 Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 30005;

int c[MAXN], t[MAXN], dq[MAXN];

int main()
{
    ifstream fin("secv3.in");
    ofstream fout("secv3.out");
    int n, l, u;
    fin >> n >> l >> u;
    for(int i = 1; i <= n; ++i){
        fin >> c[i];
        c[i] += c[i - 1];
    }
    for(int i = 1; i <= n; ++i){
        fin >> t[i];
        t[i] += t[i - 1];
    }
    int st = 0, dr = 0;
    double ans = 0.00;
    for(int i = 1; i <= n; ++i){
        while(dr >= st && dq[st] <= i - u)
            st++;
        int rez = 0, pas = 1 << 30;
        while(pas){
            int j = rez + pas;
            if(j >= dq[st] && j <= i - l + 1){
                double sec = 1.0000 * (c[i] - c[j - 1]) / (t[i] - t[j - 1]);
                ans = max(ans, sec);
                if(ans == sec)
                    rez += pas;
            }
            pas /= 2;
        }
        if(i >= l)
            dq[++dr] = i - l + 1;
    }
    fout << fixed << setprecision(2) << ans;
    return 0;
}