Cod sursa(job #914440)

Utilizator CosminRusuCosmin Rusu CosminRusu Data 14 martie 2013 09:32:06
Problema Secventa 3 Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <fstream>
#include <deque>
using namespace std;
deque <int> dq;
ifstream cin("secv3.in");
ofstream cout("secv3.out");
double cost[1005];
short timp[1005], n, l, u, i;
double sol=-((1<<31)-1);
int main()
{
    cin>>n>>l>>u;
    for(i=1;i<=n;++i)
        {
            cin>>cost[i];
            cost[i]+=cost[i-1];
        }
    for(i=1;i<=n;++i)
        {
            cin>>timp[i];
            timp[i]+=timp[i-1];
        }
    for(i=1;i<=n;++i)
        {
            while(!dq.empty() && (double)(cost[dq.back()]/timp[dq.back()])>=(double)(cost[i]/timp[i]))
                dq.pop_back();
            dq.push_back(i);
            if(i-dq.front()>=u+1)
                dq.pop_front();
            if(i-dq.front()>=l-1)
                sol=max(sol, (double)((cost[i]-cost[dq.front()])/(timp[i]-timp[dq.front()])));

        }
    cout<<sol<<"\n";
    cin.close();
    cout.close();
    return 0;
}