Cod sursa(job #1254237)

Utilizator lupuflaviu9lupuflaviu lupuflaviu9 Data 2 noiembrie 2014 13:06:20
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <deque>
#include <fstream>
#include <iomanip>
using namespace std;
ifstream fin("secv3.in");
ofstream fout("secv3.out");
const double dif= 0.001;
const int inf= (1<<30)-1+(1<<30);
const int nmax= 30000;
const int out_precision= 2;
double sol;
double a[nmax+1], b[nmax+1], spc[nmax+1];
int n, u, l;
int check( double x ) {
for ( int i= 1; i<=n; ++i ) {
spc[i]= spc[i-1]+a[i]-x*b[i];
    }deque <int> d;
    for ( int i= l; i<=n; ++i ) {
        for ( ; !d.empty() && spc[i-l]<=spc[d.back()]; d.pop_back() ) ;
        d.push_back(i-l);
        if ( d.front()==i-u-1 ) d.pop_front();
 if ( spc[i]>spc[d.front()] ) {
            return 1;
        }
    }
 return 0;
}
 
int main(  ) {
    fin>>n>>l>>u;
    for ( int i= 1; i<=n; ++i ) {
        fin>>a[i];
    }
    for ( int i= 1; i<=n; ++i ) {
        fin>>b[i];
    }
 
    double left= 0, right= inf, mid;
    while ( left<=right ) {
        mid= ((double)left+right)/2;
        if ( check(mid) ) {
            sol= mid;
            left= mid+dif;
        } else {
            right= mid-dif;
        }
    }
 
    fout<<setprecision(out_precision)<<fixed;
    fout<<sol<<"\n";
 
    return 0;
}