Cod sursa(job #1254539)

Utilizator nimicLeoveanu Mihaita Alexandru nimic Data 2 noiembrie 2014 21:27:46
Problema Secventa 3 Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <fstream>
#include <iomanip>
using namespace std;
ifstream in("secv3.in");
ofstream out("secv3.out");
 
const double mde = 0.001;
const int nmax = 30006, inf = 2000000000;
double m[nmax], v[nmax], sum[nmax], rasp;
int n, u, l;
 
bool verificare(double x)
{
    for(int i = 1; i<=n; i++)
	{
        sum[i] = sum[i - 1] + m[i] - x * v[i];
    }
 
    int d[nmax], p = 1, q = 0;
    for(int i = l; i<=n; i++) 
	{
        while(p<=q && sum[i-l]<=sum[q]) 
			q--;

		q++;
        d[q] = i - l;

        if(d[p]==i - u - 1)
			p++;
 
        if(sum[i]>sum[d[p]])
		{
            return 1;
        }
    }
 
    return 0;
}
 
void bs()
{
	double lo = 0, hi = (double)inf, mid;
    while(hi - lo>=0)
	{
        mid = (lo + hi)/2;

        if(verificare(mid)==1)
		{
            rasp = mid;
            lo = mid + mde;
        }
		else
		{
            hi = mid - mde;
        }
    }
}

int main(){
	int player_unu=0;

    in>>n>>l>>u;
    for(int i = 1; i<=n; i++) 
	{
        in>>m[i];
    }

    for(int i = 1; i<=n; i++)
	{
        in>>v[i];
    }

	bs();
 
    out<<setprecision(2)<<fixed<<rasp<<'\n';
 
    return player_unu;
}