Pagini recente » Cod sursa (job #2564027) | Istoria paginii runda/olimpici | Rating Iluk Evelyn (IlukEvelyn) | Istoria paginii runda/olimpici | Cod sursa (job #2467885)
#include <fstream>
#include <deque>
#include <iostream>
using namespace std;
ifstream fin("secv3.in");
ofstream fout("secv3.out");
deque<pair<int,int>> deq;
int a[30001], b[30001], c[30001];
int n, l, u;
void read() {
fin >> n >> l >> u;
for (int i = 1; i <= n; ++i) {
fin >> a[i];
a[i] = a[i] * 100;
}
for (int i = 1; i <= n; ++i) {
fin >> b[i];
}
}
long long maxRatio(int k) {
for (int i = 1; i <= n; ++i) {
c[i] = c[i - 1] + a[i] - k * b[i];
}
long long maxSum = -9999999999999999;
for (int i = l; i <= n; ++i) {
while (!deq.empty() && deq.back().first > c[i - l]) {
deq.pop_back();
}
if (!deq.empty() && deq.front().second == i - u + 1) {
deq.pop_front();
}
deq.emplace_back(c[i - l], i - l);
if (c[i] - deq.front().first > maxSum) {
maxSum = c[i] - deq.front().first;
}
}
deq.clear();
return maxSum;
}
int main()
{
read();
int st, dr, mi;
st = 0;
dr = 100000;
while (dr - st > 1) {
mi = (st + dr) / 2;
if (maxRatio(mi) < 0) {
dr = mi;
}
else
st = mi;
}
if (maxRatio(st) >= 0)
fout << st / 100.0 << "\n";
else
fout << dr / 100.0 << "\n";
return 0;
}