Pagini recente » Cod sursa (job #3033558) | Cod sursa (job #1896719) | Cod sursa (job #502980) | Cod sursa (job #874783) | Cod sursa (job #870903)
Cod sursa(job #870903)
#include <fstream>
#include <iostream>
#include <set>
#include <deque>
#include <iterator>
#include <algorithm>
#include <limits>
#include <cmath>
#define MAXN 30005
using namespace std;
int vCostsSums[MAXN];
int vTimesSums[MAXN];
double vPartialSums[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;
double left = 0.0f;
double right = 1000000.0;
double step = 0.001;
double X;//(double)vCostsSums[n] / vTimesSums[n];
double maxSum = numeric_limits<int>::min();
int steps = 0;
while (right-left > 0.001)
//while (fabs(maxSum) > 0.005)
{
X = (right + left)/2;
double maxSum = numeric_limits<int>::min();
deqMaxSum.push_back(0);
for (int i=1; i<=n; ++i)
{
vPartialSums[i] = vCostsSums[i] - vTimesSums[i] * X;
}
for (int i=1; i<=n-L; ++i)
{
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.0)
{
break;
}
}
deqMaxSum.clear();
if (maxSum > 0.0)
{
left = X + step;
}
else if (maxSum < -0.0)
{
right = X - step;
}
//cout << maxSum << " " << (fabs(maxSum) > 0.005f) << " " << left << " " << right << endl;
/*if (fabs(maxSum) < 0.005)
{
break;
}*/
//getchar();
steps++;
}
fout.precision(2);
fout << fixed << X << "\n";
return 0;
}