Cod sursa(job #2217145)

Utilizator Dobricean_IoanDobricean Ionut Dobricean_Ioan Data 29 iunie 2018 12:46:09
Problema Secventa 3 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <deque>
#include <fstream>
#include <iomanip>
 
using namespace std;
 
ifstream fin ("secventa3.in");
ofstream fout ("secventa3.out");
 
const int Dim = 30001;
 
int n,l,u;
double Sum[Dim],sol;
pair < int , int > A[Dim];
deque < int > D;
void CB();
 
int main() {
     
    fin >> n >> l >> u;
    for ( int i = 1; i <= n; ++i)
        fin >> A[i].first;
    for ( int i = 1; i <= n; ++i)
        fin >> A[i].second;
    CB();
    fout << fixed << setprecision(3) << sol;
}
 
bool Ok ( double value) {
     int st = 1 - u, dr = 1 - l;
  for(int i = 1; i <= n; ++i)
    Sum[i] = Sum[i - 1] + A[i].first - value * A[i].second;
  D.clear();
  for(int i = 1; i <= n; ++i, st++, ++dr) {
    if(dr >= 0) {
      while(!D.empty() && Sum[dr] <= Sum[D.back()])
        D.pop_back();
      D.push_back(dr);
    }
    if(st >= 0) {
      while(!D.empty() && D.front() < st)
        D.pop_front();
    }
    if(!D.empty() && Sum[i] >=Sum[D.front()])
      return 1;
  }
  return 0;
}
 
void CB() {
     
    int st = 1, dr = 100000,mj;
    while( st <= dr) {
        mj = (st + dr) / 2;
        if( Ok((double) mj/ 100) ) {
            st = mj + 1;
            sol = (double) mj / 100;
        }
        else
            dr = mj - 1;
    }
}