Cod sursa(job #332955)

Utilizator marinMari n marin Data 21 iulie 2009 07:38:07
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.01 kb
#include <stdio.h>
#include <assert.h>

#define maxn 200010
#define INF 30001000

int N, L, NR, i, P, U, aux1, paux1;
int A[maxn], Heap[maxn], Pos[maxn], B[maxn], SA[maxn], SB[maxn];
double maxim;


void push(int x){
	int aux;
/*	
	(SA[i]-SA[Heap[x]-1]) / (SB[i]-SB[Heap[x]-1])
	(SA[i]-SA[Heap[x/2]-1]) / (SB[i]-SB[Heap[x/2]-1])
*/
	while (x/2 && (double)(SA[i]-SA[Heap[x]-1]) / (SB[i]-SB[Heap[x]-1])>(double)(SA[i]-SA[Heap[x/2]-1]) / (SB[i]-SB[Heap[x/2]-1])){
		aux = Heap[x];
		Heap[x] = Heap[x/2];
		Heap[x/2] = aux;

		Pos[Heap[x]] = x;
		Pos[Heap[x/2]] = x/2;
		x /= 2;
	}
}

void pop(int x){
	int aux, y = 0;

	while (x != y)	{
		y = x;
/*
	(SA[i]-SA[Heap[x]-1]) / (SB[i]-SB[Heap[x]-1])
	(SA[i]-SA[Heap[y*2+1]-1]) / (SB[i]-SB[Heap[y*2+1]-1])
*/
		if (y*2<=L && (double)(SA[i]-SA[Heap[x]-1]) / (SB[i]-SB[Heap[x]-1])<(double)(SA[i]-SA[Heap[y*2]-1]) / (SB[i]-SB[Heap[y*2]-1])) x = y*2;
		if (y*2+1<=L && (double)(SA[i]-SA[Heap[x]-1]) / (SB[i]-SB[Heap[x]-1])<(double)(SA[i]-SA[Heap[y*2+1]-1]) / (SB[i]-SB[Heap[y*2+1]-1])) x = y*2+1;

		aux = Heap[x];
		Heap[x] = Heap[y];
		Heap[y] = aux;

		Pos[Heap[x]] = x;
		Pos[Heap[y]] = y;
	}
}

int main()
{
	FILE *f = fopen("secv3.in", "r");
	FILE *g = fopen("secv3.out", "w");

	fscanf(f, "%d %d %d", &N, &P, &U);

	assert(1<=N && N<=200000);

	
	for (i=1;i<=N;i++) {
		fscanf(f, "%d", &A[i]);
		SA[i] = SA[i-1] + A[i];
	}
	
	for (i=1;i<=N;i++) {
		fscanf(f, "%d", &B[i]);
		SB[i] = SB[i-1] + B[i];
	}

	for (i=P;i<=N;i++) {
	
		//bag in heap pozitia i-p+1

		L++;
		Heap[L] = i-P+1;
		Pos[i-P+1] = L;
		push(L);

		if (i>U) {
			//scot din heap pozitia i-U+1


			SA[i-U-1] = -INF;
			
			push(Pos[i-U]);
			Pos[Heap[1]] = 0;
			Heap[1] = Heap[L--];
			Pos[Heap[1]] = 1;
			if (L>1) pop(1);

		}
		
		if ((double)(SA[i]-SA[Heap[1]-1]) / (SB[i]-SB[Heap[1]-1]) > maxim) {
			maxim = (double)(SA[i]-SA[Heap[1]-1]) / (SB[i]-SB[Heap[1]-1]);
		}
		
	}
	fprintf(g,"%lf",maxim);
	fclose(f);
	fclose(g);

	return 0;
}