Cod sursa(job #870903)

Utilizator claudiumihailClaudiu Mihail claudiumihail Data 4 februarie 2013 08:26:35
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.6 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];
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;
}