fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using ld = long double;
  5.  
  6. int main() {
  7.     ios::sync_with_stdio(false);
  8.     cin.tie(nullptr);
  9.  
  10.     int n, k;
  11.     cin >> n >> k;
  12.  
  13.     vector<int> a(n + 1), b(n + 1);
  14.     for (int i = 1; i <= n; ++i) cin >> a[i];
  15.     for (int i = 1; i <= n; ++i) cin >> b[i];
  16.  
  17.     auto check = [&](ld x) -> bool {
  18.         vector<ld> pref(n + 1, 0.0L);
  19.         for (int i = 1; i <= n; ++i) {
  20.             pref[i] = pref[i - 1] + (ld)b[i] - x * (ld)a[i];
  21.         }
  22.  
  23.         ld mn = 0.0L;
  24.         for (int i = k; i <= n; ++i) {
  25.             mn = min(mn, pref[i - k]);
  26.             if (pref[i] - mn >= 0.0L) return true;
  27.         }
  28.         return false;
  29.     };
  30.  
  31.     ld lo = 0.0L, hi = 1e6L;
  32.     for (int it = 0; it < 80; ++it) {
  33.         ld mid = (lo + hi) / 2.0L;
  34.         if (check(mid)) lo = mid;
  35.         else hi = mid;
  36.     }
  37.  
  38.     cout << fixed << setprecision(3) << (double)lo << '\n';
  39.     return 0;
  40. }
  41.  
Runtime error #stdin #stdout #stderr 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
https://ideone.com/3ekbTQ
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!