Pagini recente » Cod sursa (job #627052) | Cod sursa (job #595679) | Cod sursa (job #1361962) | Cod sursa (job #2522213) | Cod sursa (job #777269)
Cod sursa(job #777269)
#include <fstream>
#include <deque>
#include <iomanip>
#define MAX 30005
#define ERR 0.01
using namespace std;
int cost[MAX], timp[MAX], n, l, u;
double c[MAX];
bool solution(double med)
{
deque<int> dq;
c[0] = 0;
for(int i = 1; i <= n; i++)
c[i] = c[i - 1] + (double)cost[i] - med * timp[i];
dq.push_front(0);
for(int i = l; i <= n; i++)
{
while(!dq.empty() && c[i - l] < c[dq.back()])
dq.pop_back();
dq.push_back(i - l);
if(dq.front() == i - u - 1) dq.pop_front();
if(c[i] - c[dq.front()] >= 0) return true;
}
return false;
}
double solve()
{
double l = 0, r = 1000, m, sol;
while(r > l)
{
m = (r + l) / 2;
if(solution(m))
{
l = m + ERR;
sol = m;
}
else
r = m - ERR;
}
return sol;
}
int main()
{
ifstream in("secv3.in"); in>>n>>l>>u;
for(int i = 1; i <= n; i++) in>>cost[i];
for(int i = 1; i <= n; i++) in>>timp[i];
ofstream out("secv3.out"); out<<fixed<<setprecision(2)<<solve(); out.close();
return 0;
}