Pagini recente » Cod sursa (job #1290537) | Cod sursa (job #106968) | w0 | Diferente pentru teorema-chineza-a-resturilor intre reviziile 80 si 89 | Cod sursa (job #1006045)
#include <fstream>
#include <iomanip>
#include <deque>
#define maxn 30001
using namespace std;
ifstream fin("secv3.in");
ofstream fout("secv3.out");
deque<int> D;
double v[maxn],t[maxn];
int n,l,u;
double hi,lo,mid;
bool check_sum (double val)
{
D.clear();
double s[maxn];
s[0]=0;
for (int i=1; i<=n; ++i)
{
s[i] = s[i-1] + v[i] - val*t[i];
}
D.push_back (0);
double maxv = s[l],current = s[l];
for (int i=l+1; i<=n; ++i)
{
while (!D.empty() && s[i-l] <= s[D.front()]) D.pop_back();
D.push_back (i-l);
if (D.front() < i-u) D.pop_front();
current = s[i] - s[D.front()];
if (current > maxv) maxv = current;
}
if (current > 0) return 1;
return 0;
}
int main()
{
fin>>n>>l>>u;
for (int i=1; i<=n; ++i)
{
fin>>v[i];
hi += v[i];
}
for (int i=1; i<=n; ++i)
{
fin>>t[i];
}
lo = -1;
hi+=1;
while (hi - lo > 0.001)
{
mid = (lo+hi)/2;
if (check_sum(mid)) lo =mid;
else hi = mid;
}
fout<<fixed<<setprecision(2)<<hi;
}