Pagini recente » Cod sursa (job #1641908) | Cod sursa (job #1078781) | Cod sursa (job #1316506) | Cod sursa (job #2164991) | Cod sursa (job #870886)
Cod sursa(job #870886)
#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 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<pair<float,int> > deqMaxSum;
float X = 1000;//(float)vCostsSums[n] / vTimesSums[n];
float maxSum = numeric_limits<int>::min();
int steps = 0;
while (fabs(maxSum) > 0.005f)
{
/*for (int i=1; i<=n; ++i)
{
vPartialRatioSums[i] = vCostsSums[i] - vTimesSums[i] * X;
//cout << vPartialRatioSums[i] << " ";
}*/
//cout << endl;
deqMaxSum.push_back(make_pair(0.0f, 0));
maxSum = numeric_limits<int>::min();
float minSum = 0.0f;
for (int i=1; i<=n-L; ++i)
{
const float vCurrentSum = vCostsSums[i] - vTimesSums[i] * X;
const float vHeadSum = vCostsSums[i+L] - vTimesSums[i+L] * X;
while (!deqMaxSum.empty() && deqMaxSum.back().first >= vCurrentSum)
{
deqMaxSum.pop_back();
}
deqMaxSum.push_back(make_pair(vCurrentSum, i));
if (deqMaxSum.front().second < i + L - U)
{
//cout << "pop " << deqMaxSum.front().first << " " << deqMaxSum.front().second << endl;
deqMaxSum.pop_front();
}
minSum = deqMaxSum.front().first;
maxSum = max(maxSum, vHeadSum - minSum);
}
deqMaxSum.clear();
//cout << maxSum << endl;
if (maxSum > 0.005f)
{
X = X + X/2;
}
else if (maxSum < -0.005f)
{
X /= 2;
}
steps++;
}
//cout << "Steps = " << steps << endl;
fout.precision(2);
fout << fixed << X << "\n";
/*it = setCandidates.insert(make_pair(3.14f, 0));
setCandidates.insert(make_pair(2.71f, 1));
setCandidates.insert(make_pair(4.71f, 2));
setCandidates.insert(make_pair(2.71f, 3));
cout << setCandidates.begin()->first << " " << setCandidates.begin()->second << endl << endl;
setCandidates.erase(it.first);
for (set<Entry>::iterator i=setCandidates.begin(); i!=setCandidates.end(); ++i)
{
cout << i->first << " " << i->second << endl;
}
cout << endl;*/
return 0;
}