fork download
  1. #include<iostream>
  2. #include<vector>
  3. using namespace std;
  4. const int MAX_N = 100'000;
  5. int a_sum[MAX_N + 1];
  6. int n, d;
  7. int l, r;
  8. bool good(double mid) {
  9. double mi = 1e18;
  10. double mi_pos = -1;
  11. for(int i = d; i <= n; i++) {
  12. int j = i - d;
  13. // cout << a_sum[j] - j * mid << endl;
  14. if(mi > a_sum[j] - j * mid) {
  15. mi = a_sum[j] - j * mid;
  16. mi_pos = j + 1;
  17. }
  18. if(a_sum[i] - i * mid >= mi) {
  19. l = mi_pos;
  20. r = i;
  21. return 1;
  22. }
  23. }
  24. cout << mi << endl;
  25. return 0;
  26. }
  27. int main() {
  28. cin >> n >> d;
  29. for(int i = 1; i <= n; i++) {
  30. int x;
  31. cin >> x;
  32. a_sum[i] = x + a_sum[i - 1];
  33. }
  34. double low = -1, hi = 100;
  35. for(int i = 0; i < 60; i++) {
  36. double mid = (low + hi) / 2;
  37. if(good(mid)) {
  38. low = mid;
  39. } else {
  40. hi = mid;
  41. }
  42. }
  43. }
Success #stdin #stdout 0s 5276KB
stdin
6 2
3 1 8 5 7 2
stdout
-181
-80
-29.5
-16.875
-10.5625
-9.77344
-9.6748
-9.66864
-9.6671
-9.66671
-9.66669
-9.66668
-9.66667
-9.66667
-9.66667
-9.66667
-9.66667
-9.66667
-9.66667
-9.66667
-9.66667
-9.66667
-9.66667
-9.66667
-9.66667
-9.66667
-9.66667
-9.66667
-9.66667
-9.66667