Cod sursa(job #1255015)

Utilizator CiurezAndreiCiurez Marius-Andrei CiurezAndrei Data 3 noiembrie 2014 23:36:41
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <fstream>

using namespace std;

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

int i, n, L, U,D[30100], c[30100], t[30100];
double s[30100], st, dr, mid, sol;

int secv(double S){
    int st, dr;
    for(int i = 1; i <= n; i ++)
        s[i] = s[i-1]+ c[i] - S*t[i];
    st = 1;
    dr = 0;
    for(int i = L; i <= n; i ++){
        while(st <= dr && s[i - L] <= s[D[dr]] )
            dr--;
        D[++dr] = i - L;
        if(i - U - 1 == D[st] )
            st++;
        if(s[i] - s[D[st]] > 0)
            return 1;
    }
    return 0;
}
int main()
{
    fin >> n >> L >> U;
    for(i = 1; i <= n; i ++)
        fin >> c[i];
    for(i = 1; i <= n; i ++)
        fin >> t[i];
    st = 0; dr = 2000000000;
    while( st <= dr){
        mid = (st + dr) / 2;
        if(secv(mid)){
            sol = st;
            st = mid + 0.001;
        }
        else
            dr = mid - 0.001;
    }
    fout << sol;
    return 0;
}