Cod sursa(job #711952)

Utilizator deneoAdrian Craciun deneo Data 12 martie 2012 21:43:33
Problema Secventa 3 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <fstream>
using namespace std;

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

int n, l, u;
double v[40000], p[40000];

double sol(double a) {
    int i, st = 1;
    double maxsum = -1, suma = 0;
    for (i = 1; i <= n; ++i) {
        suma += (v[i] - a * p[i]);
        if (suma > maxsum) maxsum = suma;
        if ((suma < 0 && i - st + 1 > l) || (i - st + 1 > u))  {
            suma -= (v[st] - a * p[st]); suma -= (v[i] - a * p[i]);
            ++st; --i;
        }
    }
    return maxsum;
}

double binary_search () {
    double i, step = 512;
    for (i = 0; step > 0.005; step /= 2) {
        if (sol(i + step) >= 0)
            i += step;
    }
    return i ;
}

int main()
{
    int i;
    fin >> n >> l >> u;
    for (i = 1; i <= n; ++i)
        fin >> v[i];
    for (i = 1; i <= n; ++i)
        fin >> p[i];
    fout.precision(2);
    fout << binary_search() << "\n";
    fout.close();
    return 0;
}