Cod sursa(job #332310)

Utilizator katakunaCazacu Alexandru katakuna Data 17 iulie 2009 13:29:49
Problema Secventa 3 Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <cstdio>

#define Nmax 30010
int n, a, b, i, p, u, st, mij, dr, sol, j;
int d[Nmax], c[Nmax], t[Nmax];
long long v[Nmax], Sum;

int cont (int X) {
	
	v[1] = 0;
	for (i = 1; i <= n; i++)
		v[i + 1] = v[i] + (long long)c[i] - (long long)X * (long long)t[i];

	Sum = v[a + 1];
	p = u = 1; d[1] = 1;
	for (i = 2; i + a <= n + 1; i++) {
		
		while (p <= u && i+a - b > d[p]) p++;
		while (p <= u && v[i] <= v[ d[u] ]) u--;
		d[++u] = i;
		
		if( v[i+a] - v[ d[p] ] >= Sum ) Sum = v[i+a] - v[ d[p] ]; 
		
	}
	
	if (Sum >= 0) return 1;
	return 0;
}

int main () {
 
	FILE *f = fopen ("secv3.in", "r");
	FILE *g = fopen ("secv3.out", "w");
	
	fscanf (f, "%d %d %d", &n, &a, &b);
	for (i = 1; i <= n; i++){
		fscanf (f, "%d", &c[i]), c[i]*= 100;
	}
	
	for (i = 1; i <= n; i++)
		fscanf (f, "%d", &t[i]);
	
	dr = 1000 * 10 +10;
	while (st <= dr) {
		mij = (st + dr) >> 1;
		
		if( cont(mij) ) {
			sol = mij;
			st = mij + 1;
		}
		
		else
			dr = mij - 1;
	}
	
	fprintf (g, "%.2lf", (double)sol / (double)100);
	
	fclose (f);
	fclose (g);	
	
	return 0;

}