Cod sursa(job #2628978)

Utilizator CosminMorarMorar Cosmin Andrei CosminMorar Data 18 iunie 2020 14:13:18
Problema Secventa 3 Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.53 kb
#include <bits/stdc++.h>
#define LIMIT 30000000.0
using namespace std;
ifstream fin("secv3.in");
ofstream fout("secv3.out");
int n, a[30100], b[30100], l, u, sp_a[30100], sp_b[30100];
deque<pair<int, int> > minn;

void add(int index) {
	while (!minn.empty()) {
		long double c1 = (long double)(sp_a[index + 1] - minn.front().first) / (long double)(sp_b[index + 1] - minn.front().second);
		long double c2 = (long double)(sp_a[index + 1] - sp_a[index]) / (long double)(sp_b[index + 1] - sp_b[index]);
		if (c1 - c2 >= 0.00001)
			break;
		minn.pop_back();
	}
	minn.push_back(make_pair(sp_a[index], sp_b[index]));
}

bool have_bigger(long double want_sum) {
	minn.clear();
	for (int i = l; i <= n; i++) {
		if (i > u) /// stergem un element daca e nevoie
			if (minn.front().first == sp_a[i - u - 1] && minn.front().second == sp_b[i - u - 1])
				minn.pop_front();
		add(i - l);
		if ((long double)(sp_a[i] - minn.front().first) / (long double)(sp_b[i] - minn.front().second) > want_sum)
			return true;
	}
	return false;
}

int main() {
	fin >> n >> l >> u;
	for (int i = 1; i <= n; i++)
		fin >> a[i];
	for (int i = 1; i <= n; i++)
		fin >> b[i];
	for (int i = 1; i <= n; i++) {
		sp_a[i] = sp_a[i - 1] + a[i];
		sp_b[i] = sp_b[i - 1] + b[i];
	}
	sp_a[0] = 1;
	sp_b[0] = 1;

	double st = -LIMIT, dr = LIMIT;
	while (dr - st >= 0.00001) {
		long double mij = (st + dr) / 2.00000;
		if (have_bigger(mij))
			st = mij + 0.00001;
		else
			dr = mij;
	}

	fout << fixed << setprecision(6) << st;
    return 0;
}