Pagini recente » Cod sursa (job #2841448) | Cod sursa (job #1653447) | Cod sursa (job #2868759) | Istoria paginii runda/simulare_shumen_2 | Cod sursa (job #2297846)
#include <iostream>
#include <fstream>
#include <vector>
#include <iomanip>
#include <deque>
using namespace std;
const float eps = 0.001;
bool secvZero(vector<float> v, int mn, int mx)
{
for(int i = 1; i < v.size(); ++i)
v[i] += v[i-1];
deque<int> d;
for(int i = 0; i < mn; ++i)
d.push_front(i);
if(v[mn-1] >= 0)
return true;
for(int i = mn; i < v.size(); ++i)
{
while(d.empty() == false && v[d.front()] > v[i-mn])
d.pop_front();
d.push_front(i-mn);
if(d.back() <= i-mx)
d.pop_back();
if(v[i] - v[d.back()] >= 0)
return true;
}
return false;
}
int main()
{
ifstream in("secv3.in");
int n, mn, mx;
in >> n >> mn >> mx;
vector<int> cost(n), timp(n);
for(int i = 0; i < n; ++i)
in >> cost[i];
for(int i = 0; i < n; ++i)
in >> timp[i];
in.close();
float rasp = 0;
float st = 0, dr = 1000, mid;
vector<float> v(n);
while(dr - st > eps)
{
mid = (st + dr) / 2;
for(int i = 0; i < n; ++i)
v[i] = cost[i] - mid * timp[i];
if(secvZero(v, mn, mx))
{
rasp = max(rasp, mid);
st = mid;
}
else
dr = mid;
}
ofstream out("secv3.out");
out << fixed << setprecision(2) << rasp;
out.close();
return 0;
}