Pagini recente » Cod sursa (job #1725816) | Cod sursa (job #263286) | Cod sursa (job #709435) | Cod sursa (job #857870) | Cod sursa (job #2563588)
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 30005;
const double EPS = 1e-3;
ifstream in ("secv3.in");
ofstream out("secv3.out");
int n, l, u;
int spa[NMAX];
int spb[NMAX];
double val[NMAX];
bool ok(double x) {
deque <int> dq;
for(int i = 1; i <= n; i++) {
val[i] = (double)spa[i] - ((double)spb[i]) * x;
}
for(int i = l; i <= n; i++) {
while(!dq.empty() && i - dq.front() + 1 > u) {
dq.pop_front();
}
while(!dq.empty() && val[dq.back()] >= val[i - l]) {
dq.pop_back();
}
dq.push_back(i - l);
if(val[i] - val[dq.front()] >= 0) {
return 1;
}
}
return 0;
}
int main() {
in >> n >> l >> u;
for(int i = 1; i <= n; i++) {
in >> spa[i];
spa[i] += spa[i - 1];
}
for(int i = 1; i <= n; i++) {
in >> spb[i];
spb[i] += spb[i - 1];
}
double st = 0, dr = 1000, last = 0;
while(dr - st >= EPS) {
double mij = (st + dr) / 2;
if(ok(mij) == 1) {
st = mij;
last = mij;
}
else {
dr = mij;
}
}
out << fixed << setprecision(2) << last << "\n";
return 0;
}