Pagini recente » Cod sursa (job #2283490) | Cod sursa (job #981595) | Cod sursa (job #1888156) | Cod sursa (job #2272051) | Cod sursa (job #803056)
Cod sursa(job #803056)
#include <fstream>
#include <deque>
#include <algorithm>
using namespace std;
ifstream fin("secv3.in");
ofstream fout("secv3.out");
deque<int> dq;
void push_dq(int x);
double get_dq(int pos);
int N, l, u;
double cost[30100], timp[30100], sum[30100];
int result;
void read_input();
double binary_search();
bool check_answer(double r);
int main() {
read_input();
fout << binary_search();
}
void read_input() {
fin >> N >> l >> u;
for (int i = 1; i <= N; ++i) {
fin >> cost[i];
}
for (int i = 1; i <= N; ++i) {
fin >> timp[i];
}
}
double binary_search() {
double lo = 0, hi = 30000000, mid;
while (lo + 0.001 <= hi) {
mid = lo + (hi - lo) / 2;
if (check_answer(mid) == true) {
lo = mid;
} else {
hi = mid;
}
}
return mid;
}
bool check_answer(double r) {
dq.clear();
double max = -0x3f3f3f3f;
for (int i = 1; i <= N; ++i) {
sum[i] = sum[i-1] + cost[i] - r * timp[i];
}
if (sum[l] >= 0) return true;
for (int i = l + 1; i <= N; ++i) {
push_dq(i - l);
if (sum[i] - get_dq(i) >= 0)
return true;
}
return false;
}
void push_dq(int x) {
while(!dq.empty() && sum[dq.back()] >= sum[x]) {
dq.pop_back();
}
dq.push_back(x);
}
double get_dq(int pos) {
while (!dq.empty() && pos - dq.front() > u) {
dq.pop_front();
}
return sum[dq.front()];
}