Pagini recente » Cod sursa (job #541936) | Cod sursa (job #2145928) | Cod sursa (job #397705) | Cod sursa (job #2401985) | Cod sursa (job #2274598)
#include <iostream>
#include <fstream>
#include <deque>
#include <iomanip>
using namespace std;
ifstream in ("secv3.in");
ofstream out ("secv3.out");
int const nmax = 30000;
double const eps = 0.001;
#define MIN(a , b) (((a) < (b)) ? (a) : (b))
#define MAX(a , b) (((a) < (b)) ? (b) : (a))
int time[5 + nmax];
int cost[5 + nmax];
double v[5 + nmax];
double sum[5 + nmax];
double sol[5 + nmax];
bool test(double val , int n , int l , int r){
for(int i = 1 ; i <= n ; i++) {
v[i] = time[i] - cost[i] * val;
}
for(int i = 1 ; i <= n ; i++) {
sum[i] = sum[i - 1] + v[i];
}
int k = r - l + 1;
deque<int> dqmin;
for(int i = 1 ; i <= n ; i++){
while(0 < dqmin.size() && sum[i] <= sum[dqmin.back()])
dqmin.pop_back();
dqmin.push_back(i);
while(0 < dqmin.size() && dqmin.front() <= i - k)
dqmin.pop_front();
sol[i] = sum[dqmin.front()];
}
for(int i = 1 ; i <= n ; i++){
if(l <= i) {
if(sol[i - l] <= sum[i])
return 1;
}
}
return 0;
}
int main()
{
int n , l , r;
in >> n >> l >> r;
for(int i = 1 ; i <= n ; i++)
in >> time[i];
for(int i = 1 ; i <= n ; i++)
in >> cost[i];
double x = 0;
for(double jump = (1 << 20) ; eps < jump ; jump /= 2){
if(test(x + jump , n , l , r) == 1)
x += jump;
}
out << setprecision(2) << fixed << x;
return 0;
}