Pagini recente » Cod sursa (job #899815) | Cod sursa (job #728500) | Cod sursa (job #2650471) | Cod sursa (job #2932703) | Cod sursa (job #2312220)
#include <bits/stdc++.h>
#define EROARE 0.001
const int MV(30005) ;
int cost[MV], timp[MV] ;
double v[MV], dp[MV], sol[MV] ;
int n, l, u ;
bool test(double val) {
register int i ;
for (i = 1 ; i <= n ; ++ i) {
v[i] = cost[i] - timp[i] * val ;
dp[i] = dp[i - 1] + v[i] ; }
std::deque <int> dq ;
int k = u - l + 1 ;
dq.push_back(0) ;
for (i = 1 ; i <= n ; ++ i) {
while (!dq.empty() && dp[dq.back()] >= dp[i])
dq.pop_back() ;
dq.push_back(i) ;
while (!dq.empty() && dq.front() <= i - k)
dq.pop_front() ;
sol[i] = dp[dq.front()] ; }
for (i = 1 ; i <= n ; ++ i)
if (i >= l)
if (sol[i - l] <= dp[i])
return true ;
return false ; }
int main() {
freopen("secv3.in", "r", stdin) ;
freopen("secv3.out", "w", stdout) ;
register int i ;
scanf("%d %d %d", &n, &l, &u) ;
for (i = 1 ; i <= n ; ++ i)
scanf("%d", cost + i) ;
for (i = 1 ; i <= n ; ++ i)
scanf("%d", timp + i) ;
double step(1LL << 20), pos(0) ;
for (step ; step > EROARE ; step /= 2) {
if (test(pos + step) == true)
pos += step ; }
printf("%.2f", pos) ;
return 0 ; }