Cod sursa(job #186850)

Utilizator sima_cotizoSima Cotizo sima_cotizo Data 28 aprilie 2008 20:45:48
Problema Secventa 3 Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.81 kb
#include <cstdio>
#include <utility>
using namespace std;
#define MAX_N 30100
#define f first
#define s second
#define mp make_pair

long long A[MAX_N], B[MAX_N], S[MAX_N];
long long L, U, i,n,mx;

inline long long max(long long a, long long b) { return a>b ? a : b; }

/*
 * ideea e sa cautam binar raspunsu
 * trebuie sa cautam:
 * S1/S2>=X => S1>=X*S2 => S1-X*S2>=0 
 * deci scadem din fiecare A[i] pe B[i]*X si apoi cautam 
 * subsecv de suma maxima cu lungime intre L si U
 * daca ea e >= 0 atunci avem X
 */

typedef pair<long long, long long> ii;
ii D[MAX_N];
long long  st, dr;

void insert(long long x, long long i) {
	if ( st==dr && st==0 ) {
		D[st=dr=1] = mp(x, i);
		return ;
	}
	while ( dr>=st && x < D[dr].f ) --dr;
	D[++dr] = mp(x, i);
}
void pop(long long x) {
	while ( st<=dr && (D[st].s > x-L || D[st].s < x-U) )
		++st;
}
void clear() { 
	long long i;
	for ( i=0; i<=dr; ++i ) 
		D[i] = mp(0,0);
	st=dr=0;
}

long long valid(long long v) {
	/*
	 * ca sa ai O(N) per validare
	 * tii un deque : 
	 * stii ca Sum[j..i] = S[i] - S[j-1] => tii  un min-deque
	 * cu elementele de la i-U..i-L
	 * merge si priority queue
	 */
	long long i;
	clear();
	S[0] = 0;
	for ( i=1; i<=n; ++i ) 
		S[i] = S[i-1] + A[i]-B[i]*v;

	for ( i=L; i<=U; ++i ) {
		if ( S[i] > 0 ) return 1;
		insert(S[i-L], i-L);
	}
	for ( i=U+1; i<=n; ++i ) {
		pop(i);
		insert(S[i-L], i-L);
		if ( S[i]-D[st].f >=0 ) return 1;
	}
	return 0;
}

int main() {
	freopen("secv3.in", "r", stdin);
	scanf("%lld %lld %lld", &n, &L, &U);
	for ( i=1; i<=n; ++i ) {
		scanf("%lld", A+i);
		A[i] *= 1000; mx = max(mx, A[i]);
	}
	for ( i=1; i<=n; ++i ) 
		scanf("%lld", B+i);

	long long tot, k;
	for ( k=1; k<mx; k<<=1 );
	for ( tot=0; k; k>>=1 ) 
		if ( tot+k<=mx && valid(tot+k) ) 
			tot += k;

	fprintf(fopen("secv3.out", "w"), "%lld.%02lld\n", tot/1000, tot%1000);
	return 0;
}