Pagini recente » Cod sursa (job #1778931) | Cod sursa (job #2296621) | Cod sursa (job #1662346) | Cod sursa (job #2056734) | Cod sursa (job #1732788)
#include <fstream>
#include <iomanip>
#include <deque>
using namespace std;
ifstream fin("secv3.in");
ofstream fout("secv3.out");
const int MAXN = 30005;
const int MAXNR = 100005;
int N, L, U;
int a[MAXN];
int b[MAXN];
int v[MAXN];
int minim[MAXN];
int rez;
deque<int> Q;
void Read();
void CautareBinara();
bool Verificare( int x );
int main()
{
Read();
CautareBinara();
fout << fixed << setprecision(2) << ((double)rez) / 100.0 << '\n';
fin.close();
fout.close();
return 0;
}
void Read()
{
int i;
fin >> N >> L >> U;
for ( i = 1; i <= N; i++ )
{
fin >> a[i];
a[i] = 100 * a[i];
}
for ( i = 1; i <= N; i++ )
fin >> b[i];
}
void CautareBinara()
{
int st = 0, dr = MAXNR, mid;
while ( st <= dr )
{
mid = ( st + dr ) / 2;
if ( Verificare(mid) )
{
st = mid + 1;
rez = mid;
}
else
dr = mid - 1;
}
}
bool Verificare( int x )
{
int i;
Q.clear();
Q.push_back(0);
for ( i = 1; i <= N; i++ )
v[i] = v[i - 1] + a[i] - ( b[i] * x );
for ( i = 1; i < N; i++ )
{
// if ( x >= 78 && x <= 83 )
// fout << "DA";
while ( !Q.empty() && i - Q.front() >= U )
Q.pop_front();
while ( !Q.empty() && v[i] <= v[Q.back()] )
Q.pop_back();
Q.push_back(i);
// int y = Q.front();
minim[i] = v[Q.front()];
}
if ( U == 0 )
for ( i = 1; i <= N; i++ )
minim[i] = v[i];
for ( i = 1; i <= N; i++ )
{
if ( v[i] - minim[i - 1] >= 0 )
return true;
if ( i <= L && v[i] >= 0 )
return true;
}
return false;
}