Pagini recente » Cod sursa (job #1929408) | Cod sursa (job #2836132) | Cod sursa (job #2701300) | Cod sursa (job #600793) | Cod sursa (job #2974377)
#include <iostream>
#include <fstream>
#include <deque>
using namespace std;
ifstream fin("secv3.in");
ofstream fout("secv3.out");
const int LMAX = 30005;
int c[LMAX],t[LMAX],c1[LMAX];
long long s[LMAX];
deque<int> dq;
bool verif(int v[], int n, int k, int w){
int i;
long long smax;
for(i=1;i<=n;i++)
s[i] = s[i-1]+(long long)v[i];
dq.push_back(0);
smax = s[k];
for(i=k+1;i<=n;i++){
while(!dq.empty() && s[i-k]<s[dq.back()])
dq.pop_back();
dq.push_back(i-k);
if(dq.front()<i-w)
dq.pop_front();
smax = max(smax, s[i]-s[dq.front()]);
}
for(i=1;i<=n;i++)
s[i] = 0;
while(!dq.empty())
dq.pop_back();
if(smax>=0)
return 1;
return 0;
}
int main()
{
int N,L,U,i,st,dr,mid,sol;
double nr;
fin >> N >> L >> U;
for(i=1;i<=N;i++){
fin >> c[i];
c[i]*=100;
c1[i] = c[i];
}
for(i=1;i<=N;i++)
fin >> t[i];
st = 0; dr = 100005; sol = 0;
while(st<=dr){
mid = (st+dr)/2;
for(i=1;i<=N;i++)
c[i] = c1[i]-mid*t[i];
if(verif(c,N,L,U)){
sol = mid;
st = mid+1;
}
else
dr = mid-1;
}
nr = (sol*1.0)/100;
fout << nr;
return 0;
}