Pagini recente » Cod sursa (job #343722) | Cod sursa (job #11324) | Cod sursa (job #2216918) | Cod sursa (job #827176) | Cod sursa (job #1255015)
#include <fstream>
using namespace std;
ifstream fin("secv3.in");
ofstream fout("secv3.out");
int i, n, L, U,D[30100], c[30100], t[30100];
double s[30100], st, dr, mid, sol;
int secv(double S){
int st, dr;
for(int i = 1; i <= n; i ++)
s[i] = s[i-1]+ c[i] - S*t[i];
st = 1;
dr = 0;
for(int i = L; i <= n; i ++){
while(st <= dr && s[i - L] <= s[D[dr]] )
dr--;
D[++dr] = i - L;
if(i - U - 1 == D[st] )
st++;
if(s[i] - s[D[st]] > 0)
return 1;
}
return 0;
}
int main()
{
fin >> n >> L >> U;
for(i = 1; i <= n; i ++)
fin >> c[i];
for(i = 1; i <= n; i ++)
fin >> t[i];
st = 0; dr = 2000000000;
while( st <= dr){
mid = (st + dr) / 2;
if(secv(mid)){
sol = st;
st = mid + 0.001;
}
else
dr = mid - 0.001;
}
fout << sol;
return 0;
}