Mai intai trebuie sa te autentifici.
Cod sursa(job #2467864)
Utilizator | Data | 5 octombrie 2019 09:47:57 | |
---|---|---|---|
Problema | Secventa 3 | Scor | 10 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva de probleme | Marime | 1.38 kb |
#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] + a[i - 1];
}
for (int i = 1; i <= n; ++i) {
fin >> b[i];
b[i] = b[i] + b[i - 1];
}
}
int maxRatio(int k) {
for (int i = 1; i <= n; ++i) {
c[i] = a[i] * 100 - k * b[i];
}
int maxSum = -99999999;
for (int i = l; i <= n; ++i) {
while (!deq.empty() && deq.back().first > c[i - l]) {
deq.pop_back();
}
if (!deq.empty() && i - deq.front().second == u + 1) {
deq.pop_front();
}
deq.emplace_back(c[i - l], i - l);
if (deq.back().first - 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;
}