Cod sursa(job #1561579)

Utilizator alexandra_udristoiuUdristoiu Alexandra Maria alexandra_udristoiu Data 4 ianuarie 2016 11:47:00
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include<fstream>
using namespace std;
int n, i, mid, st, dr, ii, jj;
int a[30005], b[30005], d[30005];
long long s[30005];
ifstream fin("secv3.in");
ofstream fout("secv3.out");
int f(int mid){
    int p = 1, u = 0;
    for(int i = 1; i <= n; i++){
        s[i] = s[i - 1] + a[i] - b[i] * mid;
        if(i >= ii){
            while(p <= u && s[ d[u] ] > s[i - ii]){
                u--;
            }
            u++;
            d[u] = i - ii;
            if(d[p] == i - jj){
                p++;
            }
            if(s[i] - s[ d[p] ] >= 0){
                return 1;
            }
        }
    }
    return 0;
}
int main(){
    fin>> n >> ii >> jj;
    for(i = 1; i <= n; i++){
        fin>> a[i];
        a[i] *= 100;
    }
    for(i = 1; i <= n; i++){
        fin>> b[i];
    }
    st = 0;
    dr = 100000;
    while(st <= dr){
        mid = (st + dr) / 2;
        if(f(mid) == 1){
            st = mid + 1;
        }
        else{
            dr = mid - 1;
        }
    }
    fout<< dr / 100 <<".";
    if(dr % 100 < 10){
        fout<< 0 << dr % 100 <<"\n";
    }
    else{
        fout<< dr % 100 <<"\n";
    }
    return 0;
}