Cod sursa(job #2333563)

Utilizator patcasrarespatcas rares danut patcasrares Data 1 februarie 2019 14:09:07
Problema Secventa 3 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1 kb
#include<bits/stdc++.h>
#define pb push_back
#define x first
#define y second
using namespace std;
ifstream fin("secv3.in");
ofstream fout("secv3.out");
const int DN=1e5+5;
int n,l,u;
double st,dr,mij,sum[DN],val;
pair<double,double>a[DN];
pair<double,int>d[DN];
int vf(double z)
{
	for(int i=1;i<=n;i++)
	{
		val=a[i].x-a[i].y*z;
		sum[i]=sum[i-1]+val;
	}
	int ds=1,dr=0;
	for(int i=1;i<=n;i++)
	{
		if(i>=l)
		{
			while(1)
			{
				if(ds>dr)
					break;
				if(sum[i-l]>d[dr].x)
					break;
				dr--;
			}
			dr++;
			d[dr]={sum[i-l],i};
		}
		while(1)
		{
			if(ds>dr)
				break;
			if(d[ds].y>=i-u)
				break;
			ds++;
		}
		if(ds<=dr)
			if(sum[i]-d[ds].x>=0)
				return 1;
	}
	return 0;
}
int main()
{
	fin>>n>>l>>u;
	for(int i=1;i<=n;i++)
		fin>>a[i].x;
	for(int i=1;i<=n;i++)
		fin>>a[i].y;
	st=0;
	dr=1000;
	while(dr-st>1e-4)
	{
		mij=(st+dr)/2;
		if(vf(mij))
			st=mij;
		else
			dr=mij;
	}
	st=(st+dr)/2;
	fout<<fixed<<setprecision(2)<<st;
}