제출 #633049

#제출 시각아이디문제언어결과실행 시간메모리
633049iomoon191Seesaw (JOI22_seesaw)C++17
0 / 100
1 ms212 KiB
#include<bits/stdc++.h> // #define int long long #define all(a) (a).begin(), (a).end() #define sz(a) (int)(a).size() #define pb push_back #define eb emplace_back #define For(i,a,b) for(int i=(a); i<=(b); ++i) #define roF(i,a,b) for(int i=(a); i>=(b); --i) #define fi first #define se second #define mod 998244353 using namespace std; // using namespace atcoder; #ifdef DEBUG__ struct db_os{ ostream& os; bool chk; template<class T> auto operator<<(T&& x){ if(!chk) os << ", "; chk=0; os << x; return *this; } }; template<class... T> void db_out(T&&... t){ (db_os{cerr, 1} << ... << t); } #define dbg(...) \ do{ \ cerr << __LINE__ << ":" << #__VA_ARGS__ << "="; \ db_out(__VA_ARGS__); \ cerr << "\n"; \ }while(0); #else #define dbg(...) #endif typedef vector<int> vi; typedef pair<int, int> pi; typedef long long ll; typedef long double ld; const int N=100005; const ll inf=0x3f3f3f3f; mt19937 rng(random_device {}()); int rand(int a){ return rng()%a; } int n, pref[N]; double cal(int l, int r){ return 1.0*(pref[r]-pref[l-1])/(r-l+1); } void rmain(){ cin >> n; For(i,0,n-1){ int x; cin >> x; pref[i+1]=pref[i]+x; } vector<pair<double, double>> vc(n); double avg=1.0*pref[n]/n; For(i,0,n-2){ int l=0, r=n-i-1; while(l < r){ int mid=(l+r+1) >> 1; if(cal(mid+1, mid+i+1) <= avg) l=mid; else r=mid-1; } vc[i].fi=cal(l+1, l+i+1); vc[i].se=cal(l+2, l+i+2); } vc[n-1].fi=vc[n-1].se=avg; sort(all(vc)); double res=inf, mx=-inf; For(i,0,n-1){ res=min(res, max(mx, avg)-vc[i].fi); mx=max(mx, vc[i].se); } cout << fixed << setprecision(50) << res; } signed main(int argc, char *argv[]){ iostream::sync_with_stdio(0); int T=1; while(T--) rmain(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...