Pagini recente » Cod sursa (job #1973405) | Cod sursa (job #2400605) | Cod sursa (job #433924) | Cod sursa (job #3181635) | Cod sursa (job #1824046)
#include <fstream>
#include <deque>
#include <iomanip>
using namespace std;
ifstream fin ("secv3.in");
ofstream fout ("secv3.out");
const int NMAX = 30010;
deque<pair<double, int>> d;
int N, L, R;
int a[NMAX], b[NMAX];
double dist[NMAX];
bool check (double x) {
for (int i = 1; i <= N; i++) {
dist[i] = dist[i - 1] + 1.00 * a[i] - x * b[i];
}
while (!d.empty())
d.pop_back();
for (int i = 1; i <= N; i++) {
while (!d.empty() && d.front().second < i - R + 1) {
d.pop_front();
}
if (i >= L) {
while (!d.empty() && d.back().first > dist[i - L]) {
d.pop_back();
}
d.push_back(make_pair(dist[i - L], i - L));
}
if (i >= L && !d.empty() && dist[i] - d.front().first >= 0.0) {
return true;
}
}
return false;
}
int main () {
fin >> N >> L >> R;
for (int i = 1; i <= N; i++) {
fin >> a[i];
}
for (int i = 1; i <= N; i++) {
fin >> b[i];
}
double left = 0, right = 1000;
for (int i = 1; i <= 20; i++) {
double mid = (left + right) / 2;
if (check (mid)) {
left = mid;
}
else {
right = mid;
}
}
fout << fixed << setprecision (2) << left;
return 0;
}