Pagini recente » Cod sursa (job #1365402) | Cod sursa (job #1976839) | Cod sursa (job #218055) | Cod sursa (job #541701) | Cod sursa (job #545581)
Cod sursa(job #545581)
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<iostream>
#include<algorithm>
#include<deque>
#include<queue>
#include<set>
#include<vector>
using namespace std;
#define II inline
#define LL long long
#define PII pair<int, int>
#define PDD pair<double, double>
#define fs first
#define ss second
#define mp make_pair
#define pb push_back
#define FOR(i, a, b) for(int i = a ; i <= b ; i++)
#define IFOR(i, a, b) for(int i = a ; i >= b ; i--)
#define FORIT(it, V) for(vector<int> :: iterator it = V.begin() ; it != V.end() ; it++)
#define all(a) a, a +
const char IN[] = {"secv3.in"};
const char OUT[] = {"secv3.out"};
const int INF = 1000000005;
const double PI = 3.14159265;
const LL NMAX = 30005;
const LL VALMAX = 1005 * 100;
LL N, L, U;
LL a[NMAX], b[NMAX];
void citi()
{
scanf("%d%d%d", &N, &U, &L);
FOR(i, 1, N) scanf("%lld", &a[i]), a[i] *= 100;
FOR(i, 1, N) scanf("%lld", &b[i]);
}
bool exista(LL x)
{
LL A[NMAX], S[NMAX] = {0};
copy(a, a + NMAX, A);
FOR(i, 1, N)
{
A[i] -= b[i] * x;
S[i] = S[i - 1] + A[i];
}
deque<LL> Dq;
FOR(i, U + 1, N)
{
if(Dq.size() && Dq.front() < i - L)
Dq.pop_front();
while(Dq.size() && S[i - U] <= S[Dq.back()])
Dq.pop_back();
Dq.push_back(i - U);
if(S[i] - S[Dq.front()] >= 0)
return 1;
}
return 0;
}
LL caut_bin()
{
LL REZ = 0, pas;
for(pas = 1 ; pas < VALMAX ; pas <<= 1);
for(; pas ; pas >>= 1)
if(REZ + pas <= VALMAX && exista(REZ + pas))
REZ += pas;
return REZ;
}
int main()
{
freopen(IN, "r", stdin);
freopen(OUT, "w", stdout);
citi();
printf("%.2lf\n", (double)caut_bin()/100);
return 0;
}