Cod sursa(job #1409944)

Utilizator stefanzzzStefan Popa stefanzzz Data 30 martie 2015 19:44:02
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <fstream>
#include <deque>
#define MAXN 30005
#define INF 2000000000000000000
using namespace std;

int n, l, u, c[MAXN], t[MAXN], v[MAXN];
long long sp[MAXN];
int st = 0, dr = 1000005, mid;

bool works(int x){
	int i;
	long long smax = -INF;
	deque<int> dq;

	for(i = 1; i <= n; i++){
		v[i] = c[i] - x * t[i];
		sp[i] = sp[i - 1] + v[i];
	}

	for(i = l; i <= n; i++){
		while(!dq.empty() && sp[i - l] <= sp[dq.back()])
			dq.pop_back();
		dq.push_back(i - l);
		while(dq.front() < i - u) dq.pop_front();

		if(sp[i] - sp[dq.front()] > smax) smax = sp[i] - sp[dq.front()];
	}

	return smax >= 0;
}
	


int main(){
	freopen("secv3.in", "r", stdin);
	freopen("secv3.out", "w", stdout);
	int i;
	
	scanf("%d %d %d", &n, &l, &u);
	for(i = 1; i <= n; i++){
		scanf("%d", &c[i]);
		c[i] *= 1000;
	}

	for(i = 1; i <= n; i++)
		scanf("%d", &t[i]);
	
	while(st < dr){
		mid = (st + dr) >> 1;
		if(works(mid)) st = mid + 1;
		else dr = mid - 1;
	}
	while(!works(st)) st--;

	printf("%d.%03d\n", st/1000, st % 1000);

	return 0;
}