Cod sursa(job #2096055)

Utilizator RaduNRadu Negovan RaduN Data 28 decembrie 2017 14:59:30
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("secv3.in");
ofstream g("secv3.out");
struct vis {
    double a, b;
};
vis v[30005];
int  h[30005];
double maxi;
int main() {
    int frecventa, n, l, u, k;
    f>>n>>l>>u;
    for(int i=1; i<=n; i++) {
        f>>v[i].a;
        v[i].a+=v[i-1].a;
    }
    for(int i=1; i<=n; i++) {
        f>>v[i].b;
        v[i].b+=v[i-1].b;
    }
    frecventa=1;
    k=0;
    maxi=v[l].a/v[l].b;
    for(int i=l; i<=n; i++) {
        while(frecventa<=k && (v[i].a-v[h[k]].a)/(v[i].b-v[h[k]].b)<(v[i].a-v[i-l].a)/(v[i].b-v[i-l].b )){
            --k;
        }
        h[++k]=i-l;
        if(i>u){
            if(h[frecventa]==i-u-1){
                ++frecventa;
            }
        }
        if(h[frecventa]==0) {
            if(maxi<v[i].a/v[i].b){
                maxi=v[i].a/v[i].b;
            }
        } else if(maxi< (v[i].a-v[h[frecventa]].a)/(v[i].b-v[h[frecventa]].b)){
            maxi=(v[i].a-v[h[frecventa]].a)/(v[i].b-v[h[frecventa]].b);
        }

    }
    g<<maxi;
    return 0;
}