Pagini recente » Cod sursa (job #1543233) | Cod sursa (job #1334948) | Cod sursa (job #2556498) | Cod sursa (job #2846973) | Cod sursa (job #937668)
Cod sursa(job #937668)
#include <fstream>
#include <deque>
#include <cmath>
#include <algorithm>
#include <iostream>
using namespace std;
const int maxn = 30100;
#define rm_front() while(!D.empty() && D.front() < i-hi )D.pop_front()
#define rm_back() while(!D.empty() && aux[i-lo] <= aux[D.back()])D.pop_back()
int cost[maxn];
int timp[maxn];
double aux[maxn];
int n,lo,hi,val;
ifstream in("secv3.in");
ofstream out("secv3.out");
deque<int> D;
bool good(int cautat){
double best=-(1<<30), fixat = 1.0*cautat/100.0;
for(register int i = 1 ; i <= n ; ++ i)
aux[i] = aux[i-1] + cost[i] - fixat * timp[i];
D.clear();
D.push_back(0);
for(register int i = lo ; i <= n ; ++ i){
rm_front();
rm_back();
D.push_back(i-lo);
best = max(best,aux[i] - aux[D.front()]);
}
return best >= -(1e-9);
}
int bsearch(){
int i,step;
val *= 100;
for(step=1;step<val;step<<=1);
for(i=0;step;step>>=1){
if(i+step <= val && good(i+step))
i += step;
}
return i;
}
int main(){
in >> n >> lo >> hi;
for(register int i = 1 ; i <= n ; ++ i){
in >> cost[i];
val = max(val,cost[i]);
}for(register int i = 1 ; i <= n ; ++ i){
in >> timp[i];
}
out.precision(2);
float show = 1.0 * bsearch() / 100.0;
out << show << "\n";
}