Cod sursa(job #1256841)

Utilizator killer301Ioan Andrei Nicolae killer301 Data 6 noiembrie 2014 22:16:01
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <cstdio>
#include <deque>

using namespace std;

const int nmax=30005;
const double eps=0.001;

int n, l, u;
double c[nmax], t[nmax], sp[nmax];
deque <int> d;

bool verif(double m)
{
    for(int i=1;i<=n;i++)
        sp[i]=sp[i-1]+c[i]-m*t[i];
    deque <int> d;
    for(int i=l;i<=n;i++)
    {
        while(!d.empty() && sp[i-l]<=sp[d.back()])
            d.pop_back();
        d.push_back(i-l);
        if(d.front()==i-u-1)
            d.pop_front();
        if(sp[i]>sp[d.front()])
            return true;
    }
    return false;
}
double bs()
{
	double last=0;
	double lf=0, rg=2000000000;
	while(lf<=rg)
	{
		double med=(lf+rg)/2;
		if(verif(med))
		{
			last=med;
			lf=med+eps;
		}
		else rg=med-eps;
	}
	return last;
}

int main()
{
    freopen("secv3.in", "r", stdin);
    freopen("secv3.out", "w", stdout);
    scanf("%d", &n);
    scanf("%d%d", &l, &u);
    for(int i=1;i<=n;i++)scanf("%lf", &c[i]);
    for(int i=1;i<=n;i++)scanf("%lf", &t[i]);
    printf("%.2lf", bs());
    return 0;
}