Cod sursa(job #2938200)

Utilizator Chiri_Robert Chiributa Chiri_ Data 11 noiembrie 2022 19:32:52
Problema Secventa 3 Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <bits/stdc++.h>

using namespace std;

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

int n, l, u;
int c[30001], t[30001];
int sc[30001], st[30001];
double smx;

int sum(int* v, int st, int sf) {
    return v[sf]-v[st-1];
}

double val(int i, int k) {
    int scost = sum(sc, i-k+1, i);
    int stimp = sum(st, i-k+1, i);
    return ((double)(scost)/stimp);
}

int main()
{
    fin >> n >> l >> u;
    for (int i = 1; i <= n; i++) {
        fin >> c[i];
        sc[i] = sc[i-1]+c[i];
    }
    for (int i = 1; i <= n; i++) {
        fin >> t[i];
        st[i] = st[i-1]+t[i];
    }

    for (int k = l; k <= u; k++) {
        deque<int> q;

        for (int i = 1; i <= n; i++) {
            while (!q.empty() && val(i, k) > val(q.back(), k)) {
                q.pop_back();
            }
            q.push_back(i);
            if (q.front() <= i-k) {
                q.pop_front();
            }
            if (i >= k) {
                smx = max(smx, val(q.front(), k));
            }
        }
    }
    fout << fixed << setprecision(2) << smx;
    return 0;
}