Pagini recente » Cod sursa (job #2096113) | Cod sursa (job #948531) | Cod sursa (job #1633889) | Cod sursa (job #134235) | Cod sursa (job #1254809)
#include <iostream>
#include <fstream>
#include <deque>
#include <iomanip>
using namespace std;
ifstream f ("secv3.in");
ofstream g ("secv3.out");
const int NMAX = 30000 + 1;
int n, l, u;
double cost[NMAX], timp[NMAX], s[NMAX];
void citeste() {
f >> n >> l >> u;
for (int i = 1; i <= n; i++) f >> cost[i];
for (int i = 1; i <= n; i++) f >> timp[i];
}
bool ok (double x) {
for (int i = 1; i <= n; i++) s[i] = s[i - 1] + cost[i] - x * timp[i];
deque <int> D;
for (int i = l; i <= n; i++) {
while (!D.empty() && s[i - l] <= s[D.back()]) D.pop_back();
D.push_back(i - l);
if (D.front() == i - u - 1) D.pop_front();
if (s[i] - s[D.front()] > 0) return true;
}
return false;
}
void rezolva() {
double st, dr, mid, sol, epsilon = 0.001;
st=0; dr=2000000000;
while (st <= dr) {
mid = (st + dr) / 2;
if (ok(mid)) {
sol = mid;
st = mid + epsilon;
}
else dr = mid - epsilon;
}
g << fixed << setprecision(2) << sol << '\n';
}
int main() {
citeste();
rezolva();
return 0;
}