Mike4235

LAH28_AVERAGE

May 11th, 2021
457
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.46 KB | None | 0 0
  1. /*#pragma GCC optimize("Ofast")
  2. #pragma GCC optimize("unroll-loops")
  3. #pragma GCC target("avx,avx2,fma")*/
  4. // only when really needed
  5.  
  6. /* GNU G++17 7.3.0: No long long for faster code
  7.    GNU G++17 9.2.0 (64 bit, msys 2): Long long only for faster code */
  8.  
  9. #include <bits/stdc++.h>
  10.  
  11. #define for1(i,a,b) for (int i = a; i <= b; i++)
  12. #define for2(i,a,b) for (int i = a; i >= b; i--)
  13. #define int long long
  14.  
  15. #define sz(a) (int)a.size()
  16. #define pii pair<int,int>
  17.  
  18. /*
  19. __builtin_popcountll(x) : Number of 1-bit
  20. __builtin_ctzll(x) : Number of trailing 0
  21. */
  22.  
  23. #define PI 3.1415926535897932384626433832795
  24. #define INF 1000000000000000000
  25. #define MOD 1000000007
  26. #define MOD2 1000000009
  27. #define EPS 1e-6
  28.  
  29. using namespace std;
  30.  
  31. double a[100005];
  32. int n, k;
  33.  
  34. signed main() {
  35.    
  36.     ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  37.  
  38.     freopen("average.inp", "r", stdin);
  39.     freopen("average.out", "w", stdout);
  40.  
  41.     cin >> n >> k;
  42.     for1(i,1,n) {
  43.         int x;
  44.         cin >> x;
  45.         a[i] = double(x);
  46.     }
  47.  
  48.     double l = 0, r = 1e9;
  49.     for1(i,1,100) {
  50.  
  51.         double m = (l + r)/2, sum = 0, sum2 = 0, mn = 0;
  52.         bool flag = false;
  53.  
  54.         for1(i,1,k) sum += a[i] - m;
  55.         for1(i,k+1,n) {
  56.             sum += a[i] - m;
  57.             sum2 += a[i - k] - m;
  58.             if (sum2 < mn) mn = sum2;
  59.             if (sum - mn + EPS > 0) flag = true;
  60.         }
  61.  
  62.         if (flag) l = m;
  63.         else r = m;
  64.  
  65.     }
  66.  
  67.     cout << fixed << setprecision(4) << l;
  68.    
  69. }
Advertisement
Add Comment
Please, Sign In to add comment