Cod sursa(job #1409922)

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

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

bool works(int x){
	int i, 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] *= 100;
	}

	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.%02d\n", st/100, st % 100);

	return 0;
}