1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| #include<bits/stdc++.h>
#define N 100010
#define eps (0.00001)
#define max(a,b) ((a)>(b)?(a):(b))
#define mem(a,b) memset(a,b,sizeof(a))
#define fsb(a,b,c) for(int a=b;a<=(c);a++)
#define fbs(a,b,c) for(int a=b;a>=(c);a--)
using namespace std;
double a[N],f[N],g[N],sum=0,l,r,md;
int n;
template<typename qw>inline void rll(qw &x){
x=0;qw f=1;char c=getchar();
while(!isdigit(c))f=c=='-'?-1:f,c=getchar();
while(isdigit(c))x=x*10+c-'0',c=getchar();
x*=f;
}
inline int check(double x){
mem(f,0);mem(g,0);int mx=0;double sum=0;
fsb(i,2,n-1){
if(f[i-1]>0){
g[i]=g[i-1];f[i]=f[i-1]+a[i]-x;
}else{
f[i]=a[i]-x;g[i]=i;
}
if(mx==0||f[mx]<f[i])mx=i;
}
fsb(i,1,g[mx]-1)sum+=a[i]-x;
fsb(i,mx+1,n)sum+=a[i]-x;
return sum<=0;
}
int main(){
rll(n);fsb(i,1,n)rll(a[i]),sum+=a[i];
l=0;r=sum;
while(l+eps<r){
md=(l+r)/2;
if(check(md))r=md;else l=md;
}
printf("%0.3lf\n",md);
return 0;
}
|