Pagini recente » Cod sursa (job #2255378) | Cod sursa (job #1020017) | Cod sursa (job #2617430) | Cod sursa (job #23835) | Cod sursa (job #2683239)
#include <iostream>
#include <fstream>
#include <deque>
#include <iomanip>
#define eps 0.01
#define NMAX 30000
using namespace std;
ifstream f("secv3.in");
ofstream g("secv3.out");
int n, l, r;
double sp[NMAX+10], a[NMAX+10];
pair <double, double> v[NMAX+10];
deque <int> dq;
bool isOK(double val)
{ while(!dq.empty()) dq.pop_back();
for(int i=1; i<=n; i++)
{ a[i] = v[i].first - val * v[i].second;
sp[i] = sp[i-1] + a[i];
while(!dq.empty() && dq.front() < i - r) dq.pop_front();
if(i >= l)
{ while(!dq.empty() && sp[dq.back()] > sp[i-l]) dq.pop_back();
dq.push_back(i-l);
if(sp[i] - sp[dq.front()] >= 0) return 1;
}
}
return 0;
}
int main()
{
f >> n >> l >> r;
for(int i=1; i<=n; i++) f >> v[i].first;
for(int i=1; i<=n; i++) f >> v[i].second;
double st = 0, dr = 1000, ans = 0;
while(dr - st > eps)
{ double mij = (st + dr) / 2;
if(isOK(mij)) ans = mij, st = mij;
else dr = mij;
}
g << setprecision(2) << fixed << ans << '\n';
return 0;
}