Pagini recente » Cod sursa (job #2480408) | Cod sursa (job #236308) | Cod sursa (job #2797227) | Cod sursa (job #639665) | Cod sursa (job #1249288)
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <deque>
#define DIM 30005
#define eps 0.001
#define INF 1500000000
#define infile "secv3.in"
#define outfile "secv3.out"
using namespace std;
ifstream f(infile);
ofstream g(outfile);
deque<int> DEQ;
double Partial_Sum[DIM], Cost[DIM], Time[DIM];
int n, l, u;
bool Check_Time(double time_to_check) {
for (int i = 1; i <= n; ++i)
Partial_Sum[i] = Partial_Sum[i - 1] + Cost[i] - Time[i] * time_to_check;
if (Partial_Sum[l] > 0)
return 1;
DEQ.clear();
for (int i = l; i <= n; ++i) {
while (!DEQ.empty() && DEQ.front() < i - u)
DEQ.pop_front();
while (!DEQ.empty() && Partial_Sum[DEQ.back()] >= Partial_Sum[i - l])
DEQ.pop_back();
DEQ.push_back(i - l);
if (Partial_Sum[i] - Partial_Sum[DEQ.front()] > 0)
return 1;
}
return 0;
}
int main() {
f >> n >> l >> u;
for (int i = 1; i <= n; ++i)
f >> Cost[i];
for (int i = 1; i <= n; ++i)
f >> Time[i];
double left = 0, right = INF, SOL;
while (left <= right) {
double mid = (left + right) / 2;
if (Check_Time(mid)) {
left = mid + eps;
SOL = mid;
}
else
right = mid - eps;
}
g << setprecision(3) << SOL;
return 0;
}
//Trust me, I'm the Doctor!