Pagini recente » Cod sursa (job #1736340) | Cod sursa (job #199909) | Cod sursa (job #2471269) | Profil deianp17 | Cod sursa (job #1702343)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <functional>
#include <string>
#include <cstring>
#include <cmath>
#include <map>
#include <set>
#include <stack>
#include <iomanip>
#define NMAX 30005
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define pb push_back
using namespace std;
typedef pair<int, int> pii;
const long double EPS=0.001;
ifstream fin("secv3.in");
ofstream fout("secv3.out");
long double c[NMAX],t[NMAX],aux[NMAX],best[NMAX];
deque<int> dq;
int main() {
int n,l,u,i,ok,k;
long double st,dr,mid;
fin>>n>>l>>u;
k=u-l+1;
for(i=1;i<=n;++i) fin>>c[i];
for(i=1;i<=n;++i) fin>>t[i];
st=0;
dr=1000;
while(abs(st-dr)>=EPS) {
mid=(st+dr)/2;
dq.clear();
ok=0;
for(i=1;i<=n;++i) {
aux[i]=aux[i-1]+c[i]-mid*t[i];
while(!dq.empty() && aux[i]<=aux[dq.back()]) dq.pop_back();
dq.pb(i);
while(i-dq.front()>=k) dq.pop_front();
best[i]=aux[dq.front()];
if(i>=l && aux[i]-best[i-l]>=0) {
ok=1;
break;
}
}
if(ok) st=mid;
else dr=mid;
}
fout<<fixed<<setprecision(3)<<st;
return 0;
}