Cod sursa(job #2906218)

Utilizator NToniBoSSNicolae Tonitza NToniBoSS Data 25 mai 2022 09:50:13
Problema Secventa 3 Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.1 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, r;
    freopen("secv3.in","r",stdin);
    freopen("secv3.out","w",stdout);
    scanf("%d%d%d", &n, &l, &r);
    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] + dist[i - 1];
        tp[i] = 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 - r)
            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;
}