Cod sursa(job #1995865)

Utilizator valentin50517Vozian Valentin valentin50517 Data 29 iunie 2017 12:30:57
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <bits/stdc++.h>
using namespace std;
int N,C[1<<15],T[1<<15],L,U;
bool check(double d){
    int l=1,r=L,ls=1;
    double c=0,cs=0;
    for(int i=1;i<L;i++) c+=C[i]-T[i]*d; 
    for(;r<=N;r++){
        c+=C[r]-T[r]*d; 
        while(cs >= 0 && r-ls+1>L) cs+=C[ls]-T[ls]*d,ls++;
        if(cs<=0) l=ls,c-=cs,cs=0; 
        while(r-l+1 > L && C[l]-T[l]*d < 0) l++,c-=C[l]-T[l]*d,cs-=(l<ls ? C[l]-T[l]*d : 0);
        if(c >= 0) return true;
    }
    return false;
}
int main(){
    ifstream cin("secv3.in");
    ofstream cout("secv3.out");
    cin >> N >> L >> U;
    for(int i = 1;i<=N;i++) cin >> C[i];
    for(int i = 1;i<=N;i++) cin >> T[i];
    double st=0,dr=1000;
    while(dr-st >= 0.001){
        double mid = (dr+st)/2.0;
        (check(mid) ? st : dr) = mid;
    }
    cout << st;
    return 0;
}