codeforces 578C Weakness and Poorness

codeforces 578C Weakness and Poorness"/>

codeforces 578C Weakness and Poorness

C. Weakness and Poorness time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output

You are given a sequence of n integers a1, a2, ..., an.

Determine a real number x such that the weakness of the sequence a1 - x, a2 - x, ..., an - x is as small as possible.

The weakness of a sequence is defined as the maximum value of the poorness over all segments (contiguous subsequences) of a sequence.

The poorness of a segment is defined as the absolute value of sum of the elements of segment.

Input

The first line contains one integer n (1 ≤ n ≤ 200 000), the length of a sequence.

The second line contains n integers a1, a2, ..., an (|ai| ≤ 10 000).

Output

Output a real number denoting the minimum possible weakness of a1 - x, a2 - x, ..., an - x. Your answer will be considered correct if its relative or absolute error doesn't exceed 10 - 6.

Sample test(s) input

3
1 2 3

output

1.000000000000000

input

4
1 2 3 4

output

2.000000000000000

input

10
1 10 2 9 3 8 4 7 5 6

output

4.500000000000000

水三分

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
using namespace std;
const double E = exp(1.0);
const double INF = 1e8;
const double eps = 1e-11;
double maxx = -INF, minn = INF;const int N = 200000 + 5;double x[N];double fun(double v, int n) {double tmp = x[0] - v, ret = x[0] - v;//cout<<x[0] - v<<' ';bool flag = 0;if(x[0] < v) flag = 1;for(int i = 1; i < n; ++i) {if(x[i] < v) flag = 1;tmp += x[i] - v;//cout<<x[i] - v<<' ';if(tmp < x[i] - v) {tmp = x[i] - v;}ret = max(tmp, ret);}//cout<<endl;//cout<<ret<<endl;if(flag) {maxx = v - x[0];tmp = v - x[0];for(int i = 1; i < n; ++i) {tmp += v - x[i];if(tmp < v - x[i]) {tmp = v - x[i];}maxx = max(tmp, maxx);}}return max(ret, maxx);
}int main() {int n;cin>>n;double x0 = 0;for(int i = 0; i < n; ++i) {cin>>x[i];maxx = max(x[i], maxx);maxx = max(-x[i], maxx);minn = min(x[i], minn);}double L = -INF, R = INF;double m_l, m_r;while (L + eps < R) {double m_l = (2 * L + R) / 3;double m_r = (L + 2 * R) / 3;double ans_l = fun(m_l, n);double ans_r = fun(m_r, n);//cout<<ans_l<<' '<<ans_r<<endl;if (ans_l > ans_r) {L = m_l;} else {R = m_r;}}double ans = (L + R) / 2;printf("%.7f\n", fun(ans, n));
}