Cod sursa(job #173723)

Utilizator varuvasiTofan Vasile varuvasi Data 7 aprilie 2008 23:39:04
Problema Secventa 3 Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.92 kb
#include <stdio.h>
#define maxn 40000
//#define INF 2000000001
#define FOR(i, a, b) for (i = (a); i <= (b); i++)

long long INF = 1e12;
long long N, L, U;
long long kmax = 0, smax, sum, st, dr;
long long c[maxn], t[maxn], best[maxn], sump[maxn], b[maxn], coada[maxn];

FILE *fin = fopen("secv3.in", "rt"), *fout = fopen("secv3.out", "wt");
void calc()
{
	long long i, j, jmax, maxim = -INF;
	sum = sump[L];
	FOR(i, L+1, N)
	{
		sum += b[i];
		if (i - st + 1 > L)
		{
			maxim = sum, jmax = st;
			FOR(j, st + 1, (i - L + 1))
				if (sump[i] - sump[j - 1] > maxim)
					maxim = sump[i] - sump[j - 1], jmax = j;
			sum = maxim;
			st = jmax;
		}
/*		if (i - st + 1 > U)
		{
			sum -= b[st];
			maxim = -INF;
			FOR(j, st + 1, st + (U - L + 1))
				if (sump[i] - sump[j - 1] > maxim)
					maxim = sump[i] - sump[j - 1], jmax = j;
			sum = maxim;
			st = jmax;
		}*/
		if (sum > smax) smax = sum;
	}
	if (sum > smax) smax = sum;
}

int proc(long long k)
{
	int i;
//	fprintf(fout, "%lld\n", k);
	FOR(i, 1, N) b[i] = c[i] - k*t[i];
	FOR(i, 1, N) sump[i] = sump[i - 1] + b[i];
/*	FOR(i, 1, N)
		fprintf(fout, "%lld ", b[i]);
	fprintf(fout, "\n");
	FOR(i, 1, N)
		fprintf(fout, "%lld ", sump[i]);
	fprintf(fout, "\n");*/
	smax = sump[L], sum = 0, st = 1, dr = 0;
	/*FOR(i, L + 1, N) 
		addq(i);*/
	calc();
//	fprintf(fout, "%lld\n", smax);
	if (smax >= 0) return 1;
	else 		  return 0;
}

void cbin()
{
	long long lf = 0, rt = INF, mij = 0;
	while (lf <= rt)
	{
		mij = (lf + rt) >> 1;
//		fprintf(fout, "%lld\n", mij);
		if (proc(mij)) 
		{
			lf = mij + 1;
			kmax = mij;
		}
		else 
			rt = mij - 1;
//		fprintf(fout, "%lld %lld\n", lf, rt);
	}
}

int main()
{
	int i;
	fscanf(fin, "%lld %lld %lld", &N, &L, &U);
	FOR(i, 1, N)
		fscanf(fin, "%lld", &c[i]), c[i] *= 100;
	FOR(i, 1, N)
		fscanf(fin, "%lld", &t[i]);
//	FOR(i, 1, N)
//		fprintf(fout, "%lld %lld\n", c[i], t[i]);
	cbin();
	fprintf(fout, "%.2f", (double)kmax/100.0);
	fclose(fin), fclose(fout);
	return 0;
}