Pagini recente » Cod sursa (job #641884) | Cod sursa (job #81130) | Cod sursa (job #789914) | Cod sursa (job #1095918) | Cod sursa (job #1556775)
#include <fstream>
#include <queue>
using namespace std;
ifstream in("secv3.in");
ofstream out("secv3.out");
const int MAX_N = 30000;
const int BSLIM = 100000;
int n, l, u;
int A[1 + MAX_N];
int B[1 + MAX_N];
long long D[1 + MAX_N];
void build_array(int X) {
int i;
for(i = 1; i <= n; i++) {
D[i] = D[i-1] + A[i] * 100 - X * B[i];
}
}
bool bs_check(int X) {
int i;
deque < long long > minQ;
build_array(X);
for(i = 1; i <= n; i++) {
if(!minQ.empty() && minQ.front() < i - u) {
minQ.pop_front();
}
if(i - l >= 0) {
while(!minQ.empty() && D[i-l] <= D[minQ.back()]) {
minQ.pop_back();
}
minQ.push_back(i-l);
}
if(!minQ.empty()) {
if(D[i] - D[minQ.front()] >= 0) return 1;
}
}
return 0;
}
int b_search() {
int l = 1, r = BSLIM, m, best = -1;
while(l <= r) {
m = (l + r) / 2;
if(bs_check(m) == 1) {
best = m;
l = m + 1;
}
else r = m - 1;
}
return best;
}
int main() {
int i;
in >> n >> l >> u;
for(i = 1; i <= n; i++) in >> A[i];
for(i = 1; i <= n; i++) in >> B[i];
out << (double)b_search() / 100 << '\n';
return 0;
}