Pagini recente » Cod sursa (job #3347744) | Cod sursa (job #3333732) | Monitorul de evaluare | Cod sursa (job #2236718) | Cod sursa (job #3338271)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>
using namespace std;
ifstream fin("secv3.in");
ofstream fout("secv3.out");
const int MAXN = 30002;
double C[MAXN], T[MAXN], Val[MAXN];
int Deque[MAXN];
int N, L, U;
bool verif(double B) {
int front = 1;
int back = 0;
Val[0] = 0.0;
for (int i = 1; i <= N; ++i) {
Val[i] = C[i] - B * T[i];
// pop i - U
if (front <= back && Deque[front] <= i - U) {
++front;
}
// push i - L
if (i >= L) {
while (front <= back && Val[i - L] <= Val[Deque[back]]) --back;
Deque[++back] = i - L;
}
if (front <= back && Val[Deque[front]] <= Val[i]) return true;
}
return false;
}
int main()
{
fin >> N >> L >> U;
for (int i = 1; i <= N; ++i) {
fin >> C[i];
C[i] += C[i - 1];
}
for (int i = 1; i <= N; ++i) {
fin >> T[i];
T[i] += T[i - 1];
}
double sol = 0.0;
for (double v = 1.0; v >= 0.01; v /= 2.0) {
if (verif(sol + v)) sol += v;
}
fout << fixed << setprecision(2) << sol;
return 0;
}
// ( C[i] - C[j] ) / (T[i] - T[j]) >= B
// C[i] - C[j] >= B (T[i] - T[j])
// C[i] - B * T[i] >= C[j] - B * T[j]