Cod sursa(job #2903061)

Utilizator NToniBoSSNicolae Tonitza NToniBoSS Data 17 mai 2022 01:44:52
Problema Secventa 3 Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <bits/stdc++.h>
/// TONI BO$$ was here
/// #MLC

using namespace std;

int dist[100001], tp[100001], deq[100001];

int main()
{
    int n, l, u, i, d, t, j, p;
    freopen("secv3.in","r",stdin);
    freopen("secv3.out","w",stdout);
    scanf("%d%d%d", &n, &l, &u);
    for(i = 1; i <= n; i++)
        scanf("%d", &dist[i]);
    for(i = 1; i <= n; i++)
        scanf("%d", &tp[i]);
    for(i = 1; i <= n; i++)
    {
        dist[i] += dist[i - 1];
        tp[i] += tp[i - 1];
    }
    double maxv = (double)(dist[l]) / tp[l];
    deq[p = u = 1] = 1;
    for(i = l + 1; i <= n; i++)
    {
        while(p <= u && deq[i] <= i - u)
            p++;
        while(p <= u && (double)(dist[i] - dist[deq[u] - 1]) / (tp[i] - tp[deq[u] - 1]) < (double)(dist[i] - dist[i - l]) / (tp[i] - tp[i - l]))
            u--;
        deq[++u] = i - l + 1;
        if(maxv < (double)(dist[i] - dist[deq[p] - 1]) / (tp[i] - tp[deq[p] - 1]))
            maxv = (double)(dist[i] - dist[deq[p] - 1]) / (tp[i] - tp[deq[p] - 1]);
    }
    printf("%.2lf\n", maxv);

    return 0;
}