Pagini recente » Cod sursa (job #1705461) | Monitorul de evaluare | Cod sursa (job #3312394) | Borderou de evaluare (job #2504406) | Cod sursa (job #3311787)
#include <bits/stdc++.h>
#define NMAX 30002
using namespace std;
ifstream fin("secv3.in");
ofstream fout("secv3.out");
int N,L,U;
int S[NMAX],T[NMAX];
bool is_better(double x)
{
deque <int> dq;
for(int i=L;i<=N;i++){
int j = i-L + 1;
while(!dq.empty() && T[dq.back()-1] - x*S[dq.back() - 1] <= T[j-1] - x * S[j-1]){
dq.pop_back();
}
dq.push_back(j);
while(dq.front() <= i-U+1){
dq.pop_front();
}
j = dq.front();
if(T[i] - x*S[i] > T[j-1] - x*S[j-1]){
// cout << j << " , " << i << "\n";
return true;
}
}
return false;
}
double caut_bin()
{
double ret = 0;
double left = 0;
double right = 1002;
int it = 60;
while(it--){
double mid = (left + right)/2.;
if(is_better(mid)){
ret = mid;
left = mid;
}else{
right = mid;
}
}
return ret;
}
int main()
{
fin >> N >> L >> U;
for(int i=1;i<=N;i++){
fin >> T[i];
T[i]+=T[i-1];
}
for(int i=1;i<=N;i++){
fin >> S[i];
S[i]+=S[i-1];
}
// cout << is_better(1) << "\n";
fout << fixed << setprecision(2)<< caut_bin();
}