이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
const int maxn=2000000+10;
long long all[maxn],ps[maxn],n;
long double md;
pair<long double,long double>stf[maxn];
long double calmian(int len,int l){
int r=l+len-1;
if(r>n){
return 1e9+5;
}
long double ret=ps[r]-ps[l-1];
ret/=len;
return ret;
}
void calstf(int ind){
int low=1,high=n+1,mid;
while(high-low>1){
mid=(high+low)>>1;
if(calmian(ind,mid)<=md){
low=mid;
}
else{
high=mid;
}
}
stf[ind].first=calmian(ind,low);
stf[ind].second=calmian(ind,high);
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>all[i];
ps[i]=ps[i-1]+all[i];
}
md=(long double)ps[n]/n;
long double mx=md;
vector<pair<long double,int>>v;
for(int i=1;i<=n;i++){
calstf(i);
v.push_back(make_pair(stf[i].first,i));
}
sort(v.rbegin(),v.rend());
long double res=1e9;
while((int)v.size()>0){
//cout<<mx<<" "<<v.back().first<<" "<<v.back().second<<endl;
res=min(res,mx-v.back().first);
mx=max(mx,stf[v.back().second].second);
v.pop_back();
}
cout<<setprecision(10)<<fixed<<res<<endl;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |