Cod sursa(job #2266507)

Utilizator maria_sinteaMaria Sintea maria_sintea Data 22 octombrie 2018 18:50:41
Problema Secventa 3 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <iostream>
#include <cstdio>
#include <deque>
#define N 30001

using namespace std;

int n, lmin, lmax, c[N], t[N];
deque <int> q1;
deque <double> q2;

int main()
{
    freopen("secv3.in", "r", stdin);
    freopen("secv3.out", "w", stdout);

    scanf("%d %d %d\n", &n, &lmin, &lmax);
    for(int i=0;i<n;i++)
        scanf("%d ", &c[i]);
    for(int i=0;i<n;i++)
        scanf("%d ", &t[i]);

    for(int l=lmin;l<=lmax;l++)
    {
        int sc=0, st=0;
        for(int i=0;i<l;i++)
        {
            q1.push_back(i);
            sc+=c[i];
            st+=t[i];
        }
        for(int i=l;i<n;i++)
        {
            int x=q1.front();
            while(!q1.empty() && (sc-c[x]+c[i])*1.0/(st-t[x]+t[i])>sc*1.0/st)
            {
                sc=sc-c[x]+c[i];
                st=st-t[x]+t[i];
                q1.pop_front();
                x=q1.front();
            }
            q1.push_back(i);
        }
        while(!q2.empty() && q2.back()<sc*1.0/st)
            q2.pop_back();
        q2.push_back(sc*1.0/st);
    }
    printf("%.2llf", q2.front());
    return 0;
}