Cod sursa(job #525979)

Utilizator darrenRares Buhai darren Data 26 ianuarie 2011 21:53:41
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.8 kb
#include <fstream>
#include <iomanip>
#include <algorithm>

using namespace std;

int N, L, U;
pair<int, int> V[30002], Sp[30002];
double maxv = -1;

int main()
{
    ifstream fin("secv3.in");
    ofstream fout("secv3.out");

    fin >> N >> L >> U;
    for (int i = 1; i <= N; ++i)
    {
        fin >> V[i].first;
        Sp[i].first = Sp[i - 1].first + V[i].first;
    }
    for (int i = 1; i <= N; ++i)
    {
        fin >> V[i].second;
        Sp[i].second = Sp[i - 1].second + V[i].second;
    }

    pair<int, int> now(V[1]);
    int pbeg = 1, len = 1;

    if (L == 1)
        maxv = double(now.first) / double(now.second);

    for (int i = 2; i <= N; ++i)
    {
        ++len;
        now.first += V[i].first, now.second += V[i].second;

        while (len > U)
        {
            now.first -= V[pbeg].first, now.second -= V[pbeg].second;
            ++pbeg;
            --len;
        }
        while (len > L && V[pbeg].first * now.second <= V[pbeg].second * now.first)
        {
            now.first -= V[pbeg].first, now.second -= V[pbeg].second;
            ++pbeg;
            --len;
        }

        if (len > L)
        {
            int aux = len - L;
            if ((Sp[pbeg + aux - 1].first - Sp[pbeg - 1].first) * now.second <= (Sp[pbeg + aux - 1].second - Sp[pbeg - 1].second) * now.first)
                while (len > L)
                {
                    now.first -= V[pbeg].first, now.second -= V[pbeg].second;
                    ++pbeg;
                    --len;
                }
        }

        if (len >= L)
        {
            double value = double(now.first) / double(now.second);
            maxv = max(maxv, value);
        }
    }

    fout << fixed << setprecision(3) << maxv;

    fin.close();
    fout.close();
}