Cod sursa(job #2879)

Utilizator surcauvsurcau vasile surcauv Data 19 decembrie 2006 18:43:58
Problema Secventa 3 Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 kb
# include <stdio.h>
# include <string.h>

# define  maxn  30002
# define  maxs  131072

# define  _fin  "secv3.in"
# define  _fout "secv3.out"


int c[maxn], t[maxn], l, u, n;
int sol;


void readf()
{
	FILE *fin = fopen(_fin, "r");
	int  i;
	
	for (fscanf(fin, "%d %d %d", &n, &l, &u), i=1; i<=n; i++)
		 fscanf(fin, "%d", c+i), c[i] *= 100;
	for (i=1; i<=n; i++)
		 fscanf(fin, "%d", t+i);
		 
	fclose(fin);
}

int deque[maxn], st, dr;	// stanga / dreapta cozii
int aux[maxn];

int pozsum(int val)
{
	int i;
	
	for (i=1; i<=n; i++)
		aux[i] = aux[i-1] + c[i] - val * t[i];
		
	// inseram in deque primele l-1 elemente
	
	st=1, dr=0;
	memset(deque, 0, sizeof(deque));
	
	for (i=1; i<=n; i++)
	{
		if ( i-l >= 1 )
		{
			while ( aux[ deque[dr] ] > aux[ i-l ] && dr >= st ) dr--;
			
			deque[ ++dr ] = i-l;
		}
		
		if ( i-u-1 >= 1 )
			// scoatem elementul din varful listei
			if ( deque[ st ] == i-u-1 ) ++st;
		
		if ( aux[ i ] - aux[ deque[ st ] ] >= 0 && i >= l ) return 1;
	}
	
	return 0;
}

void solve()
{
	int i, step = maxs;
	
	for (i=0; step; step>>=1)
		if ( pozsum(i + step) )
			i += step;
			
	sol = i;
}

void writef()
{
	FILE *fout = fopen(_fout, "w");
	fprintf(fout, "%d.%d\n", sol/100, sol%100), fclose(fout);
}

int main()
{
	readf();
	solve();
	writef();
	
	return 0;
}