Cod sursa(job #2550082)

Utilizator SchnitzelMannPavaloiu Gabriel SchnitzelMann Data 18 februarie 2020 13:02:56
Problema Secventa 3 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.56 kb
#include <bits/stdc++.h>
#define N 30002
using namespace std;
ifstream in("secv3.in");
ofstream out("secv3.out");
int a[N],b[N],d[N],n,j,k,i;
float s[N];
bool ok(float x)
{
	int l=1,r=0,i;
	for(i=1;i<=n;i++)
		s[i]=s[i-1]+a[i]-x*b[i];
	for(i=j;i<=n;i++)
	{
		if(l<=r&&d[l]==i-k)
			l++;
		while(l<=r&&s[i-j]<s[d[r]])
			r--;
		d[++r]=i-j;
		if(s[i]-s[d[l]]>=0)
			return 1;
	}
	return 0;
}
int main()
{
	float r=0,pas;
	in>>n>>j>>k;
	for(i=1;i<=n;i++)
		in>>a[i];
	for(i=1;i<=n;i++)
		in>>b[i];
	for(pas=1<<9;pas>0.005;pas/=2)
		if(ok(r+pas))
			r+=pas;
	out<<r;
	return 0;
}