Pagini recente » Cod sursa (job #921322) | Cod sursa (job #551202) | Cod sursa (job #2612122) | Cod sursa (job #3226294) | Cod sursa (job #1388977)
#include <fstream>
#include <deque>
#include <iomanip>
using namespace std;
ifstream fin("secv3.in");
ofstream fout("secv3.out");
const double eps = 1e-2;
int N, U, L;
int cost[30005], timp[30005];
double sol, sp[30005];
deque<int> DQ;
bool solve(double x)
{
DQ.clear();
sp[1] = cost[1] - x * timp[1];
for (int i = 2; i <= N; ++i)
sp[i] = sp[i - 1] + cost[i] - x * timp[i];
for (int i = L; i <= N; ++i)
{
while (!DQ.empty() && sp[DQ.back() - 1] >= sp[i - L + 1]) // minimul
DQ.pop_back();
DQ.push_back(i - L + 1);
while (DQ.front() < i - U + 1)
DQ.pop_front();
if (sp[i] - sp[DQ.front() - 1] >= eps)
return true;
}
return false;
}
int main()
{
fin >> N >> L >> U;
for (int i = 1; i <= N; ++i)
fin >> cost[i];
for (int i = 1; i <= N; ++i)
fin >> timp[i];
double lt = 0.0, rt = 30000000.0;
while (rt - lt > eps)
{
double mid = (lt + rt) / 2.0;
if (solve(mid))
{
lt = mid;
sol = mid;
}
else
rt = mid;
}
fout << fixed << setprecision(2) << sol << '\n';
fin.close();
fout.close();
return 0;
}