Cod sursa(job #1702343)

Utilizator pas.andreiPopovici Andrei-Sorin pas.andrei Data 15 mai 2016 01:25:40
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <functional>
#include <string>
#include <cstring>
#include <cmath>
#include <map>
#include <set>
#include <stack>
#include <iomanip>
#define NMAX 30005
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define pb push_back

using namespace std;

typedef pair<int, int> pii;

const long double EPS=0.001;

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

long double c[NMAX],t[NMAX],aux[NMAX],best[NMAX];
deque<int> dq;

int main() {
	int n,l,u,i,ok,k;
	long double st,dr,mid;

	fin>>n>>l>>u;
	k=u-l+1;

	for(i=1;i<=n;++i) fin>>c[i];
	for(i=1;i<=n;++i) fin>>t[i];

	st=0;
	dr=1000;
	while(abs(st-dr)>=EPS) {
		mid=(st+dr)/2;

		dq.clear();
		ok=0;
		for(i=1;i<=n;++i) {
			aux[i]=aux[i-1]+c[i]-mid*t[i];

			while(!dq.empty() && aux[i]<=aux[dq.back()]) dq.pop_back();
			dq.pb(i);

			while(i-dq.front()>=k) dq.pop_front();

			best[i]=aux[dq.front()];
			if(i>=l && aux[i]-best[i-l]>=0) {
				ok=1;
				break;
			}
		}

		if(ok) st=mid;
		else dr=mid;
	}

	fout<<fixed<<setprecision(3)<<st;

	return 0;
}