Cod sursa(job #1741664)

Utilizator TimitocArdelean Andrei Timotei Timitoc Data 14 august 2016 17:50:03
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <iostream>
#include <cstdio>
#define MAXN 30050

using namespace std;

int lu, uu, n;
int val[MAXN], t[MAXN];
int deck[MAXN], st, dr;

void read()
{
	scanf("%d %d %d", &n, &lu, &uu);
    for (int i = 1; i <= n; i++)
		scanf("%d", &val[i]);
	for (int i = 1; i <= n; i++)
		scanf("%d", &t[i]);
}
double EPS = 0.0001;
double sum[MAXN];

int check(double exp)
{
	sum[0] = 0;
	for (int i = 1; i <= n; i++)
        sum[i] = sum[i-1] + val[i] - exp*t[i];
	st = 0; dr = 0;
    for (int i = lu; i <= n; i++)
    {
		while (st < dr && sum[i-lu] < sum[deck[dr-1]])
			dr--;
		deck[dr++] = i-lu;
		if (i - deck[st] > uu)
			st++;
        if (sum[i] - sum[deck[st]] >= 0)
            return 1;
    }
    return 0;
}

void solve()
{
	double lo = EPS, hi = 30000000;
    while (hi-lo > EPS)
	{
        double mid = (lo + hi) / 2;
        if (check(mid))
			lo = mid;
        else
			hi = mid;
	}
    printf("%.2lf", lo);
}

int main()
{
    freopen("secv3.in", "r", stdin);
    freopen("secv3.out", "w", stdout);

    read();
    solve();

    return 0;
}