Cod sursa(job #870884)

Utilizator claudiumihailClaudiu Mihail claudiumihail Data 4 februarie 2013 07:19:32
Problema Secventa 3 Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.1 kb
#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 = (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;
}