Pagini recente » Cod sursa (job #2323188) | Cod sursa (job #825266) | Cod sursa (job #2680440) | Cod sursa (job #2148070) | Cod sursa (job #3304926)
#include <fstream>
#include <iomanip>
#include <deque>
using namespace std;
ifstream fin("secv3.in");
ofstream fout("secv3.out");
const int Nmax = 30000 + 5;
long long cost[Nmax], timp[Nmax], sp[Nmax], l, u, n;
bool valid( int x )
{
int i;
for ( i = 1; i <= n; ++i )
sp[i] = sp[i - 1] + cost[i] * 100 - x * timp[i];
deque <int> deq;
for ( i = l; i <= n; ++i )
{
if ( deq.front() < i - u )
deq.pop_front();
while ( deq.empty() == false && sp[deq.back()] > sp[i - l] )
deq.pop_back();
deq.push_back(i - l);
if ( sp[i] - sp[deq.front()] >= 0 )
return true;
}
return false;
}
int main()
{
int i;
fin >> n >> l >> u;
for ( i = 1; i <= n; ++i )
fin >> cost[i];
for ( i = 1; i <= n; ++i )
fin >> timp[i];
long long st = 0, dr = 3 * 1e7 * 100, mij, sol = 0;
while ( st <= dr )
{
mij = (st + dr) / 2;
if ( valid(mij) == true )
{
sol = mij;
st = mij + 1;
}
else
dr= mij - 1;
}
fout << fixed << setprecision(2) << sol / 100.0;
return 0;
}