Pagini recente » Cod sursa (job #1113653) | Cod sursa (job #761158) | Cod sursa (job #1696023) | Cod sursa (job #740507) | Cod sursa (job #186839)
Cod sursa(job #186839)
#include <cstdio>
#include <utility>
using namespace std;
#define MAX_N 30100
#define f first
#define s second
#define mp make_pair
int A[MAX_N], B[MAX_N], S[MAX_N];
int L, U, i,n,mx;
inline int max(int a, int 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<int, int> ii;
ii D[MAX_N];
int st, dr;
void insert(int x, int 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(int x) {
while ( st<=dr && (D[st].s >= x-L || D[st].s <= x-U) )
++st;
}
void clear() {
int i;
for ( i=0; i<=dr; ++i )
D[i] = mp(0,0);
st=dr=0;
}
int valid(int 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
*/
int 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("%d %d %d", &n, &L, &U);
for ( i=1; i<=n; ++i ) {
scanf("%d", A+i);
A[i] *= 100; mx = max(mx, A[i]);
}
for ( i=1; i<=n; ++i )
scanf("%d", B+i);
int 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"), "%d.%d\n", tot/100, tot%100);
return 0;
}