Pagini recente » Cod sursa (job #1872837) | Cod sursa (job #874761) | Cod sursa (job #2108338) | Cod sursa (job #1340137) | Cod sursa (job #1783051)
#include <fstream>
#include <deque>
using namespace std;
ifstream fin("secv3.in");
ofstream fout("secv3.out");
const int NMAX = 30069, RMAX = 1<<30;
const double eps = 1.e-2;
int c[NMAX], t[NMAX];
int n, l, u;
double check(double x){
double p[NMAX], sp[NMAX], sum_secv, max_sum = -1.00 * (double)RMAX;
deque<int> q;
int i;
for(i = 1; i <= n; ++i){
p[i] = (double)c[i] - x * (double)t[i];
sp[i] = sp[i - 1] + p[i];
}
for(i = 1; i <= n; ++i){
if(i-l+1 > 0){
while(!q.empty() && sp[q.back()] >= sp[i - l]){
q.pop_back();
}
q.push_back(i - l);
while(!q.empty() && q.front() <= i - u - 1){
q.pop_front();
}
sum_secv = sp[i] - sp[q.front()];
max_sum = max(max_sum, sum_secv);
}
}
return max_sum;
}
int Bin_search(int lf, int r){
int m, x;
while(lf < r){
m = (lf + r) / 2;
if(check((double)m / 100.00) >= 0){
lf = m + 1;
x = m;
}
else{
r = m - 1;
}
}
return x;
}
int main()
{
int i;
fin>>n>>l>>u;
for(i = 1; i <= n; ++i){
fin>>c[i];
}
for(i = 1; i <= n; ++i){
fin>>t[i];
}
fout<<(double)Bin_search(0, RMAX) / 100;
return 0;
}