Cod sursa(job #173430)

Utilizator varuvasiTofan Vasile varuvasi Data 7 aprilie 2008 19:28:10
Problema Secventa 3 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.68 kb
#include <stdio.h>
#define maxn 30001
#define INF 1001
#define FOR(i, a, b) for (i = (a); i <= (b); i++)

int 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 addq(int pos)
{
	if (pos == 1) 
		coada[dr++] = pos, sum = c[pos];
	else
	{
		if (sum + c[pos] > 0)
		{
			sum += c[pos];
			coada[dr++] = pos;
		}
		while (dr - st > U - L)
			sum -= c[coada[st]], st++;
		while (sum < 0 && st < dr)
			sum -= c[coada[st]], st++;
	}
	if (smax < sump[pos] - sump[pos - L])
		smax = sump[pos] - sump[pos - L];
	if (smax < sum + sump[coada[pos]] - sump[coada[pos] - L])
		smax = sump[coada[st]] - sump[coada[st] - L];
}

int proc(int k)
{
	int i;
//	fprintf(fout, "%d\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, "%d ", b[i]);
	fprintf(fout, "\n");
	FOR(i, 1, N)
		fprintf(fout, "%d ", sump[i]);
	fprintf(fout, "\n");*/
	smax = sump[L], sum = 0, st = 0, dr = 0;
	FOR(i, L + 1, N) 
		addq(i);
//	fprintf(fout, "%d\n", smax);
	if (smax >= 0) return 1;
	else 		  return 0;
}

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

int main()
{
	int i;
	fscanf(fin, "%d %d %d", &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, "%d %d\n", c[i], t[i]);*/
	cbin();
	fprintf(fout, "%.2f", (double)kmax/100.0);
	fclose(fin), fclose(fout);
	return 0;
}