Pagini recente » Cod sursa (job #1378381) | Cod sursa (job #567862) | Cod sursa (job #1607728)
#include <fstream>
#include <iomanip>
#include <iostream>
using namespace std;
const int MAX_N = 30000;
int S[2][MAX_N + 1];
int D[MAX_N];
int main() {
ifstream fin("secv3.in");
ofstream fout("secv3.out");
fin.tie(0);
ios_base::sync_with_stdio(false);
int N, L, U; fin >> N >> L >> U;
for (int i = 0; i <= 1; ++ i) {
for (int j = 1; j <= N; ++ j) {
fin >> S[i][j]; S[i][j] += S[i][j - 1];
}
}
fin.close();
double st = .0, fn = 3e7 + 1, mid;
while (fn - st > 1e-4) {
mid = st + (fn - st) * 0.5;
int lo = 0, hi = 0;
bool pass = false;
int i = L;
do {
const double curr = S[0][i - L] - mid * S[1][i - L];
while (lo != hi && S[0][D[hi - 1]] - mid * S[1][D[hi - 1]] > curr) {
hi--;
if (hi == -1) {
hi = N - 1;
}
}
D[hi++] = i - L;
if (hi == N) {
hi = 0;
}
if (D[lo] < i - U) {
lo++;
if (lo == N) {
lo = 0;
}
}
pass |= (S[0][i] - mid * S[1][i] >= S[0][D[lo]] - mid * S[1][D[lo]]);
} while (++ i <= N && !pass);
if (pass) {
st = mid;
} else {
fn = mid;
}
}
fout << fixed << setprecision(2) << st << '\n';
fout.close();
return 0;
}