Cod sursa(job #2912278)

Utilizator euyoTukanul euyo Data 7 iulie 2022 20:22:48
Problema Secventa 3 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

ifstream fin( "secv3.in" );
ofstream fout( "secv3.out" );

const int MAXN = 30005;
const int COEF = 1000;

ll a[MAXN], b[MAXN];
ll S[MAXN], n, L, U;

bool chk( ll R ) {
  for ( int i = 1; i <= n; ++i ) {
	S[i] = S[i - 1] + a[i] * COEF - R * b[i];
  }
  deque<ll> dq;
  for ( int i = L; i <= n; ++i ) {
    while ( dq.size() && dq.back() > S[i - L] ) {
	  dq.pop_back();
	}
	dq.push_back( S[i - L] );
    if ( i >= U && dq.front() == S[i - U] ) {
	  dq.pop_front();
	}
	if ( dq.size() && S[i] - dq.front() >= 0 ) {
	  return true;
	}
  }
  return false;
}

ll bs() {
  ll l = 0, r = 1e6;
  
  while ( r - l > 1 ) {
	ll mid = (l + r) / 2;
    if ( chk(mid) ) {
	  l = mid;
	} else {
	  r = mid;
	}
  }
  return l;
}

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];
  }
  fout << setprecision(3) << fixed << (double)bs() / COEF;
  fin.close();
  fout.close();
  return 0;
}