fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. #define fi first
  5. #define se second
  6. #define siz(x) (int)(x.size())
  7. #define all(x) x.begin(), x.end()
  8. #define debug_arr(x,len) for(int _=1; _<=len; _++) cout<<x[_]<<" "; cout<<'\n';
  9. #define debug(x) cout<<'\n'<<#x<<": "<<x<<'\n';
  10. const int maxN = 1e6+5;
  11.  
  12. int n;
  13. double a[maxN], b[maxN];
  14. double cal(double x)
  15. {
  16. 	for(int i=1; i<=n; i+=1) b[i] = a[i] - x;
  17. 	double tmp = 0, res1 = 0, res2 = 0;
  18. 	for(int i=1; i<=n; i+=1)
  19. 	{
  20. 		if(tmp < 0) tmp = 0;
  21. 		tmp += b[i];
  22. 		res1 = max(res1, tmp);
  23. 	}
  24. 	for(int i=1; i<=n; i+=1) b[i] = -b[i];
  25. 	tmp = 0;
  26. 	for(int i=1; i<=n; i+=1)
  27. 	{
  28. 		if(tmp < 0) tmp = 0;
  29. 		tmp += b[i];
  30. 		res2 = max(res2, tmp);
  31. 	}
  32. 	return max(res1, res2);
  33. }
  34.  
  35. int32_t main()
  36. {
  37. 	ios_base::sync_with_stdio(0); cin.tie(0);
  38. 	cin>>n;
  39. 	for(int i=1; i<=n; i+=1) cin>>a[i];
  40. 	double l = -1e18, r = 1e18;
  41. 	while(r - l > 1e-6)
  42. 	{
  43. 		double mid = (l+r) / 2;
  44. 		if(cal(mid) >= cal(mid+1e-6)) l = mid;
  45. 		else r = mid;
  46. 	}
  47. 	cout<<fixed<<setprecision(6)<<min(cal(l),cal(r))<<'\n';
  48. }
Success #stdin #stdout 0.01s 5312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0.000000
https://ideone.com/bf28nv
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

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!