Pagini recente » Cod sursa (job #3260287) | Cod sursa (job #609821) | Cod sursa (job #1901127) | Cod sursa (job #2791875) | Cod sursa (job #3161048)
//oftica si durere in suflet
#include <fstream>
#include <climits>
#include <deque>
#include <cfloat>
#define ll long long
using namespace std;
const int NMAX = 30000;
const int BULAN = 30;
const double EPS = 0.00001;
//0.832513
//0.833292
int s1[NMAX + 1];
int s2[NMAX + 1];
int n, l, u;
double s3[NMAX + 1]; //s1(i) - s2(i) * val
bool ok(double val) //daca exista secventa care sa aiba valoarea aia >= val
{
int i;
for (i = 1; i <= n; i++)
{
s3[i] = s1[i] - s2[i] * val;
}
deque <int> d;
for (i = 1; i <= n; i++)
{
while (!d.empty() and d.front() < i - u)
d.pop_front();
if (i - l >= 1)
{
while (!d.empty() and s3[d.back()] > s3[i - l])
d.pop_back();
d.push_back(i - l);
}
if (!d.empty())
{
if (s3[i] >= s3[d.front()])
return true;
}
}
return false;
}
signed main()
{
ifstream cin("secv3.in");
ofstream cout("secv3.out");
int i;
cin >> n >> l >> u;
for (i = 1; i <= n; i++)
{
int x;
cin >> x;
s1[i] = s1[i - 1] + x;
}
for (i = 1; i <= n; i++)
{
int x;
cin >> x;
s2[i] = s2[i - 1] + x;
}
double med, st = 0, dr = 1000;
double sol = -1;
for (i = 1; i <= BULAN and (st <= dr); i++)
{
med = ((st + dr) / 2);
if (ok(med))
{
sol = med;
st = med + EPS;
}
else
dr = med - EPS;
}
cout << sol;
}