Cod sursa(job #3216)

Utilizator m_dersidanDersidan Mihai m_dersidan Data 22 decembrie 2006 09:25:06
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 kb
# include <stdio.h>
# include <string.h>

# define  maxn  30002
# define  maxs  131072

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

# define  myint long long

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


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

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

myint pozsum(myint val)
{
	myint 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()
{
	myint i, step = maxs;
	
	for (i=0; step; step>>=1)
		if ( pozsum(i + step) )
			i += step;
			
	sol = i;
}

void writef()
{
	double rez = (double) sol / 100.0;
	FILE *fout = fopen(_fout, "w");
	fprintf(fout, "%.2f\n", rez), fclose(fout);
}

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