Pagini recente » Cod sursa (job #2065463) | Cod sursa (job #1510881) | Cod sursa (job #1391418) | Cod sursa (job #837163) | Cod sursa (job #1834541)
#include <fstream>
#include <queue>
using namespace std;
const int BSLIM = 100000;
int n,l,u,i,v[30005],w[30005];
long long p[30001];
void build_array(int x)
{
int i;
for(i=1; i<=n; i++)
{
p[i]=p[i-1]+v[i]*100-x*w[i];
}
}
bool bs_check(int X)
{
int i;
deque <long long> q;
build_array(X);
for(i=1; i<=n; i++)
{
if(!q.empty()&&q.front()<i-u)
{
q.pop_front();
}
if(i-l>=0)
{
while(!q.empty()&&p[i-l]<=p[q.back()])
{
q.pop_back();
}
q.push_back(i-l);
}
if(!q.empty())
{
if(p[i]-p[q.front()]>=0) return 1;
}
}
return 0;
}
int b_search()
{
int st=1,dr=100000,m,best=-1;
while(st<=dr)
{
m=(st+dr)/2;
if(bs_check(m)==1)
{
best=m;
st=m+1;
}
else dr=m-1;
}
return best;
}
int main()
{
ifstream f("secv3.in");
ofstream g("secv3.out");
f>>n>>l>>u;
for(i=1; i<=n; i++) f>>v[i];
for(i=1; i<=n; i++) f>>w[i];
g<<(double)b_search()/100<< '\n';
f.close(); g.close();
return 0;
}