Pagini recente » Cod sursa (job #933302) | Cod sursa (job #2600359) | Cod sursa (job #186503) | Cod sursa (job #1962281) | Cod sursa (job #186845)
Cod sursa(job #186845)
#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<int, int> 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] *= 100; 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/100, tot%100);
return 0;
}