Pagini recente » Cod sursa (job #2095220) | Cod sursa (job #2938044) | Cod sursa (job #2736658) | Cod sursa (job #1291875) | Cod sursa (job #994534)
Cod sursa(job #994534)
#include <deque>
#include <cstdio>
using namespace std;
const int MAX_N = 30002;
const double EPS = 0.01;
int N, L, U;
double C[MAX_N], T[MAX_N], S[MAX_N];
deque < pair < double, double > > D;
double sol;
inline int double_cmp(double a, double b) {
if(a - b < -EPS)
return -1;
if(a - b > EPS)
return 1;
return 0;
}
inline bool check(double R) {
while(!D.empty())
D.pop_front();
for(int i = 1; i < L; ++i)
S[i] = S[i-1] + C[i] - R*T[i];
for(int i = L, j = 0; i <= N; ++i, ++j) {
while(!D.empty() && S[j] <= D.back().first)
D.pop_back();
D.push_back(make_pair(S[j], j));
while(!D.empty() && D.front().second <= i-U)
D.pop_front();
S[i] = S[i-1] + C[i] - R*T[i];
double Best = S[i] - D.front().first;
if(double_cmp(Best, 0.0) >= 0)
return 1;
}
return 0;
}
int main() {
freopen("secv3.in", "r", stdin);
freopen("secv3.out", "w", stdout);
scanf("%d %d %d", &N, &L, &U);
for(int i = 1; i <= N; ++i)
scanf("%lf", &C[i]);
for(int i = 1; i <= N; ++i)
scanf("%lf", &T[i]);
double l = 0, m = 0, r = 1000000.0;
while(double_cmp(l, r) <= 0) {
m = (l+r)/2.0;
if(check(m))
sol = m, l = m+EPS;
else r = m-EPS;
}
printf("%.2lf\n", sol);
return 0;
}