Pagini recente » Cod sursa (job #1672885) | Cod sursa (job #1362600) | Arhiva de probleme | Cod sursa (job #49145) | Cod sursa (job #870895)
Cod sursa(job #870895)
#include <fstream>
#include <iostream>
#include <set>
#include <deque>
#include <iterator>
#include <algorithm>
#include <limits>
#include <cmath>
#define MAXN 30001
using namespace std;
typedef pair<float,int> Entry;
int vCostsSums[MAXN];
int vTimesSums[MAXN];
float vPartialSums[MAXN];
float vPartialRatioSums[MAXN];
int main()
{
int n, L, U;
fstream fin("secv3.in", fstream::in);
fstream fout("secv3.out", fstream::out);
fin >> n >> L >> U;
//cout << n << " " << L << " " << U << endl;
for (int i=1; i<=n; ++i)
{
fin >> vCostsSums[i];
vCostsSums[i] += vCostsSums[i-1];
//cout << vCostsSums[i] << " ";
}
//cout << endl;
for (int i=1; i<=n; ++i)
{
fin >> vTimesSums[i];
vTimesSums[i] += vTimesSums[i-1];
//cout << vTimesSums[i] << " ";
}
//cout << endl;
deque<int> deqMaxSum;
float left = 0.0f;
float right = 1000000.0f;
float step = 0.001f;
float X;//(float)vCostsSums[n] / vTimesSums[n];
float maxSum = numeric_limits<int>::min();
int steps = 0;
while (fabs(maxSum) > 0.005f)
{
X = (right + left)/2;
deqMaxSum.push_back(0);
maxSum = numeric_limits<int>::min();
for (int i=1; i<=n; ++i)
{
vPartialSums[i] = vCostsSums[i] - vTimesSums[i] * X;
}
for (int i=1; i<=n-L; ++i)
{
const float vHeadSum = vCostsSums[i+L] - vTimesSums[i+L] * X;
while (!deqMaxSum.empty() && vPartialSums[deqMaxSum.back()] >= vPartialSums[i])
{
deqMaxSum.pop_back();
}
deqMaxSum.push_back(i);
if (deqMaxSum.front() < i + L - U)
{
//cout << "pop " << deqMaxSum.front().first << " " << deqMaxSum.front().second << endl;
deqMaxSum.pop_front();
}
maxSum = max(maxSum, vPartialSums[i+L] - vPartialSums[deqMaxSum.front()]);
if (maxSum > 0.005f)
{
break;
}
}
deqMaxSum.clear();
//cout << maxSum << endl;
//getchar();
if (maxSum > 0.005f)
{
left = X + step;
}
else if (maxSum < -0.005f)
{
right = X - step;
}
steps++;
}
fout.precision(2);
fout << fixed << X << "\n";
return 0;
}