Pagini recente » Cod sursa (job #1541917) | Cod sursa (job #2684537) | Cod sursa (job #20558) | Cod sursa (job #1207386) | Cod sursa (job #1146279)
#include <iostream>
#include <fstream>
#include <iomanip>
#include <deque>
#define DN 30005
using namespace std;
ifstream f("secv3.in");
ofstream g("secv3.out");
int n,l,u,v[DN],t[DN];
deque < int > q;
void read(){
f>>n>>l>>u;
for(int i=1;i<=n;++i)
f>>v[i];
for(int i=1;i<=n;++i)
f>>t[i];
}
bool check(double timp){
double S[DN];
S[0] = 0;
for(int i=1;i<=n;++i)
S[i]= S[i-1] + 1.0 * v[i] - 1.0 * t[i] * timp;
q.clear();
if(S[l] >= 0)
return true;
for(int i = l;i<=n;++i){
while( q.size() && S[ q.back() ] >= S[ i - l ])
q.pop_back();
while( q.size() && q.front() < i - u)
q.pop_front();
q.push_back( i - l);
if(S[i] - S[ q.front() ] >= 0)
return true;
}
return false;
}
void solve(){
double st = 0 , dr = 2000 , mij , rez;
while( st<=dr ){
mij = ( st + dr)*0.5;
cout<<mij<<" "<<check(mij)<<endl;
if(check(mij)){
rez = mij;
st = mij + 1e-2;
}else
dr = mij - 1e-2;
}
g<< fixed << setprecision(2)<<rez;
}
int main()
{
read();
solve();
return 0;
}