Pagini recente » Cod sursa (job #246247) | Cod sursa (job #1349435) | Cod sursa (job #676561) | Cod sursa (job #3209874) | Cod sursa (job #1993424)
#include <iostream>
#include <fstream>
#include <deque>
#include <iomanip>
using namespace std;
int N, L, U;
int cost [30002];
int timp [30002];
double medii [30002];
double sum [30002];
int interval[30002];
deque <pair <int, int> > D;
int main ()
{
int i, k;
ifstream in ("secv3.in");
ofstream out ("secv3.out");
pair <int, int> x;
bool posibil;
in>>N>>L>>U;
k=U-L+1;
for (i=1;i<=N;++i)
in>>cost[i];
for (i=1;i<=N;++i)
in>>timp[i];
//cout<<endl;
double lo = 0, hi = 30000001, mid;
while(hi-lo>=0.01)
{
mid = (lo + hi)/2;
posibil = false;
//cout<<lo<<" "<<mid<<" "<<hi<<"\n";
for(i=1;i<=N;++i)
{
medii[i]=cost[i]-mid*(double)timp[i];
sum[i]=sum[i-1]+medii[i];
//cout<<sum[i]<<" ";
}
//cout<<"\n";
while(!D.empty())
D.pop_front();
for(i=1;i<=N;++i)
{
x.first = i;
x.second = sum[i];
if(!D.empty() && D.front().first <= i-k)
D.pop_front();
while (!D.empty() && D.back().second >=x.second)
{
D.pop_back();
}
D.push_back(x);
interval[i]=D.front().first; //pozitia minimului din intervalu care se termina pe pozitia i
}
//cout<<"\n"<<D.empty();
for(i=L;i<=N;++i)
{
if(sum[i]-sum[interval[i-L]] >= 0) //se poate un rezultat mai mare
posibil=true;
}
if(posibil)
lo=mid;
else
hi=mid;
}
//cout<<mid;
out<<fixed<<setprecision(2)<<mid;
}