Pagini recente » Cod sursa (job #675849) | Istoria paginii utilizator/redoxgfxx | Cod sursa (job #3209845) | Cod sursa (job #970971) | Cod sursa (job #386951)
Cod sursa(job #386951)
#include <cstdio>
#include <deque>
using namespace std;
#define MAX_N 30000
#define val first
#define poz second
int N, L, U, M;
int A[MAX_N], B[MAX_N], C[MAX_N];
long long S[MAX_N];
void citire()
{
scanf("%d %d %d",&N, &L, &U);
for(int i = 1; i <= N; ++i)
{
scanf("%d",A+i);
A[i] *= 100;
M = max(M, A[i]);
}
M *= 10;
for(int i = 1; i <= N; ++i)
scanf("%d",C+i);
}
int search(int K)
{
long long ANS = -M;
for(int i = 1; i <= N; ++i)
S[i] = S[i-1] + A[i] - K*C[i];
deque <pair<long long, int> > Q;
for(int i = L; i <= N; ++i)
{
while(!Q.empty() && Q.back().val > S[i - L]) Q.pop_back();
while(!Q.empty() && Q.front().poz < i - U) Q.pop_front();
Q.push_back(make_pair(S[i - L], i - L));
if(S[i] - Q.front().val > ANS)
ANS = S[i] - Q.front().val;
}
return (ANS > 0);
}
void solve()
{
int i, lg;
for(lg = 1; lg <= M; lg <<= 1);
for(i = 0; lg; lg >>= 1)
if(i + lg <= M && search(i + lg))
i += lg;
double rez = (double) i / 100;
printf("%.2f\n",rez);
}
int main()
{
freopen("secv3.in","rt",stdin);
freopen("secv3.out","wt",stdout);
citire();
solve();
}