Submission #13687784

---

Source Code Expand

#include <bits/stdc++.h>
#define LL long long
#define db long double
using namespace std;
template <typename T> void read(T &x){
	x = 0; int f = 1; char ch = getchar();
	while (!isdigit(ch)) {if (ch == '-') f = -1; ch = getchar();}
	while (isdigit(ch)) {x = x * 10 + ch - '0'; ch = getchar();}
	x *= f;
}
inline void write(int x){if (x > 9) write(x/10); putchar(x%10+'0'); }

const int N = 200050;
int n; LL a[N],b[N],tmp[N],preb[N],prebi[N];
inline void init(){
	int i,id = 1;
	read(n);
	for (i = 1; i <= n; ++i) read(a[i]);
	for (i = 1; i <= n; ++i) read(b[i]);
	for (i = 1; i <= n; ++i) if (a[i] > a[id]) id = i;
	if (id != 1){
		--id;
		for (i = 1; i <= n; ++i) tmp[i] = a[i];
		for (i = 1; i <= n; ++i) a[(i<=id?i+n-id:i-id)] = tmp[i];
		for (i = 1; i <= n; ++i) tmp[i] = b[i];
		for (i = 1; i <= n; ++i) b[(i<=id?i+n-id:i-id)] = tmp[i];
	}
	a[n+1] = a[1],b[n+1] = b[1];
	a[0] = a[n],b[0] = b[n];
	for (i = 1; i <= n+1; ++i) preb[i] = preb[i-1] + b[i],prebi[i] = prebi[i-1] + b[i] * i;
}
inline db calc(int l,int r,int m){
	if (l == r) return a[l];
	db k = r-l,b = (db)(2.0) * (r) * (preb[r-1]-preb[l]) - (db)(2.0) * (prebi[r-1] - prebi[l]),y = a[r] - a[l],x = (y - b) / k;
	return a[l] + (m-l) * x + (db)(2.0) * (m) * (preb[m-1]-preb[l]) - (db)(2.0) * (prebi[m-1] - prebi[l]);
}
int stk[N],top; db ans,mx[N];
int main(){
	init();
	int i,j,ll,rr;
	stk[0] = 1;
	for (i = 1; i <= n+1; ++i){
		while (top && calc(stk[top-1],i,stk[top]) >= calc(stk[top-1],stk[top],stk[top])) --top;
		stk[++top] = i;
	}
	for (i = 0; i <= top; ++i){
		ll = stk[i],rr = stk[i+1];
		for (j = ll; j <= rr && j <= n; ++j) mx[j] = max(mx[j],calc(ll,rr,j));
	}
	for (i = 1; i <= n; ++i) ans += mx[i];//,cerr << i << ' ' << mx[i] << '\n';
	ans /= n;
	cout << fixed << setprecision(20) << ans << '\n';
	return 0;
}

Submission Info

Judge Result