Cod sursa(job #870899)

Utilizator claudiumihailClaudiu Mihail claudiumihail Data 4 februarie 2013 08:16:49
Problema Secventa 3 Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.63 kb
#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];
float 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;
    
    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(right-left) > 0.001 && fabs(maxSum) > 0.005f)
    while (fabs(maxSum) > 0.005f)
    {
        X = (right + left)/2;
        float 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.005f)
            {
                break;
            }
        }
        deqMaxSum.clear();

        if (maxSum > 0.005f)
        {
            left = X + step;
        }
        else if (maxSum < -0.005f)
        {
            right = X - step;
        }
        
        //cout << maxSum << " " << (fabs(maxSum) > 0.005f) << " " << left << " " << right << endl;
        
        if (fabs(maxSum) < 0.005f)
        {
            break;
        }
        //getchar();

        steps++;
    }

    fout.precision(2);
    fout << fixed << X << "\n";
    
    return 0;
}