Cod sursa(job #1505707)

Utilizator tudi98Cozma Tudor tudi98 Data 19 octombrie 2015 17:55:09
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include <fstream>
#include <deque>
using namespace std;

const int Nmax = 30000;

int c[Nmax+1],t[Nmax+1];
long long b[Nmax+1];
int N,L,U;
deque<int> D;

bool f(int x)
{
	for (int i = 1; i <= N; i++)        
		b[i] = b[i-1] + c[i] - t[i] * x;

	D.clear();

	for (int i = L; i <= N; i++)
	{
		while (!D.empty() && i - D.front() > U)
			D.pop_front();
		while (!D.empty() && b[i-L] <= b[D.back()])
			D.pop_back();

		D.push_back(i-L);

		if (b[i] - b[D.front()] >= 0)
			return 1;
	}

	return 0;
}

int main()
{
	ifstream fin("secv3.in");
	ofstream fout("secv3.out");

	fin >> N >> L >> U;

	for (int i = 1; i <= N; i++)
		fin >> c[i];

	for (int i = 1; i <= N; i++)
		fin >> t[i];

	for (int i = 1; i <= N; i++)
		c[i] *= 1000;
		                                      
	int i = 0;
	int step = 1;
	for (; step <= 1000000; step <<= 1);            
	for (; step; step >>= 1)
		if (i+step <= 1000000 && f(i+step))
			i += step;
		
	fout << (double)i/1000 << "\n";	
	
}