Cod sursa(job #2640183)

Utilizator DenisONIcBanu Denis Andrei DenisONIc Data 5 august 2020 15:32:44
Problema Secventa 3 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.97 kb
#include<bits/stdc++.h>
#define NMAX 20001
#define ld long double
#define pii pair<int,int>
using namespace std;

int n, l, u, a[NMAX], b[NMAX];
ld c[NMAX];


bool OK(ld x){
	for (int i=1;i<=n;i++){
		c[i] = a[i] - x * b[i];
		c[i] += c[i-1];
	}

	deque<pair<ld,int> > s;

	for (int i=l;i<=n;i++){
		while (!s.empty() && s.back().first > c[i-l]) s.pop_back();

		s.push_back({(ld)c[i-l], i-l});
		if (s.front().second < i - u){
			s.pop_front();
		}

		if (c[i] - s.front().first > 0){
			return true;
		}
	}
	return false;
}


int main(){
    freopen("secventa3.in", "r", stdin);
    freopen("secventa3.out", "w", stdout);
	cin >> n >> l >> u;
	for (int i=1;i<=n;i++) cin >> a[i];
	for (int i=1;i<=n;i++) cin >> b[i];

	ld st = 0, dr = 1e9,mid;

	for (int i=1;i<=200;i++){
		mid = (st + dr) / 2;
		if (OK(mid)){
			st = mid;
		}
		else{
            dr = mid;
		}
	}

	cout << fixed << setprecision(7) << st << '\n';


	return 0;
}