Pagini recente » Cod sursa (job #59892) | Cod sursa (job #2529932) | Cod sursa (job #3166919) | Cod sursa (job #1700387) | Cod sursa (job #1732797)
#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;
long long N, L, U;
long long a[MAXN];
long long b[MAXN];
long long v[MAXN];
long long minim[MAXN];
long long rez;
long long k;
deque<long long> Q;
void Read();
void CautareBinara();
bool Verificare( long long x );
int main()
{
Read();
CautareBinara();
double x = rez;
x /= 100;
fout << x << '\n';
fin.close();
fout.close();
return 0;
}
void Read()
{
long long i;
fin >> N >> L >> U;
k = U - L;
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()
{
long long st = 50, dr = 100, mid;
while ( st <= dr )
{
mid = ( st + dr ) / 2;
if ( Verificare(mid) )
{
st = mid + 1;
rez = mid;
}
else
dr = mid - 1;
}
}
bool Verificare( long long x )
{
long long 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 = L; i <= N; i++ )
{
// if ( x == 389 )
// fout << "DA";
while ( !Q.empty() && i - Q.front() > U )
Q.pop_front();
while ( !Q.empty() && v[i - L] <= v[Q.back()] )
Q.pop_back();
Q.push_back(i - L);
if ( v[i] - v[Q.front()] >= 0 )
return true;
}
return false;
}