Pagini recente » Cod sursa (job #1101149) | Cod sursa (job #873113) | Cod sursa (job #1434361) | Cod sursa (job #1343241) | Cod sursa (job #1068408)
#include <iostream>
#include <fstream>
#include <deque>
#include <iomanip>
using namespace std;
const int Nmax = 30001;
int timp[Nmax];
int cost[Nmax];
double v[Nmax];
double sum[Nmax];
deque <int> deck;
int N, L, U;
int valid( double cst )
{
double maxim = -10000000000.0f;
for ( int i = 1; i <= N; ++i )
{
v[i] = 1.0 * cost[i] - 1.0 * timp[i] * cst;
sum[i] = sum[i - 1] + v[i];
}
deck.clear();
for ( int i = L; i <= N; ++i )
{
while ( deck.size() && sum[ deck.back() ] >= sum[i - L] ) deck.pop_back();
while ( deck.size() && deck.front() < i - U ) deck.pop_front();
deck.push_back( i - L );
maxim = max( maxim, sum[i] - sum[ deck.front() ] );
}
return ( maxim >= 0.0 );
}
double cautare_binara()
{
double sol = 0;
double st = 0;
double dr = 1000;
double m;
while ( dr - st > 0.01 )
{
m = ( st + dr ) / 2.0;
if ( valid( m ) )
{
sol = m;
st = m;
}
else
{
dr = m;
}
}
return sol;
}
int main()
{
ifstream f("secv3.in");
ofstream g("secv3.out");
f >> N >> L >> U;
for ( int i = 1; i <= N; ++i )
{
f >> cost[i];
}
for ( int i = 1; i <= N; ++i )
{
f >> timp[i];
}
g << fixed << setprecision( 2 );
g << cautare_binara();
return 0;
}