Pagini recente » Cod sursa (job #1993135) | Cod sursa (job #2916347) | Cod sursa (job #1807905) | Cod sursa (job #634091) | Cod sursa (job #658553)
Cod sursa(job #658553)
#include <fstream>
#include <iomanip>
#include <deque>
#define MAXN 30010
using namespace std;
ifstream f("secv3.in");
ofstream g("secv3.out");
int n,c[MAXN],t[MAXN],i,l,u;
double r[MAXN],sol;
deque<int> Mind;
void push(int i) {
while (!Mind.empty() && r[i]<=r[Mind.back()]) Mind.pop_back();
Mind.push_back(i);
}
int query(int i) {
i=max(i-u,0);
while (!Mind.empty() && Mind.front()<i) Mind.pop_front();
return Mind.front();
}
bool possible (double v) {
Mind.clear();
for (i=1;i<=n;i++)
r[i]=r[i-1]+c[i]-t[i]*v;
for (i=l;i<=n;i++) {
push(i-l);
int q=query(i);
if (r[i]>=r[q]) return true;
}
return false;
}
void bin_search() {
double m,p=0,u=100000;
while (u-p>0.001) {
m=p+(u-p)/2;
if (possible(m)) {
sol=m;
p=m+0.0001;
}
else u=m-0.0001;
}
}
int main () {
f >> n >> l >> u;
for (i=1;i<=n;i++) f >> c[i];
for (i=1;i<=n;i++) f >> t[i];
bin_search();
g << fixed;
g << setprecision(2) << sol << '\n';
f.close();g.close();
return 0;
}