Submission #1217295

#TimeUsernameProblemLanguageResultExecution timeMemory
1217295Adeeb_obedoSeesaw (JOI22_seesaw)C++20
1 / 100
2098 ms165924 KiB
#include<bits/stdc++.h> #define int long long #define ld double #define _1 first #define _2 second #define yes cout<<"Yes\n" #define nah cout<<"No\n" #define FFF ios_base::sync_with_stdio(0);cin.tie(0); #define ipr pair<ld,ld> #define ret return #define intt int32_t #define mid ((l+r)/2) #define pb push_back #define lll __int128 using namespace std; int tst, ts; intt mo = 998244353, dx[] = {0, 1, 0, -1}, dy[] = {-1, 0, 1, 0}; int mul( int x, int y ) { ret ( ( x % mo ) * ( y % mo ) ) % mo; ret x*y; } int pwo( int x, int y ) { int res = 1; for( int i = 63; i + 1; i-- ) res = mul( res, res * ( ( 1ll << i )&y ? x : 1 ) ); ret res; } int dvii( int x, int y ) { ret mul( x, pwo( y, mo - 2 ) ); } int oo( char x ) { ret ( int )x - '0'; } int lgg( int x, int y ) { int u = 0; while( x ) { u++; x /= y; } ret u; } int mun( int x, int y ) { while( x < y )x += mo; ret ( x - y ) % mo; } int add( int x, int y ) { ret x + y - ( mo * ( x + y >= mo ) ); ret x + y; } int lcm( int x, int y ) { ret ( x * y ) / __gcd( x, y ); } #define endl '\n'; const int M =2007, N = 2e5+ 7, N2 = 5e3 + 7, inf = 2e18+7 ; double n,a[N],s,k,dp[M][M]; map<pair<ipr,ipr>,double>mp; void sol(int l,int r,ld mx,ld mn,ld su){ pair<ipr,ipr>p={{l,r},{mx,mn}}; if(mp.count(p)) ret; if(l==r){ mx=max(mx,a[l]); mn=min(mn,a[l]); mp[p]=mx-mn; //cout<<mp[p]<<endl; ret; } double q=r-l+1; double u=su-a[l],o=su-a[r]; su/=q;mx=max(mx,su),mn=min(mn,su); sol(l+1,r,mx,mn,u); sol(l,r-1,mx,mn,o); if(mp[{{l+1,r},{mx,mn}}]<mp[{{l,r-1},{mx,mn}}]) mp[p]=mp[{{l+1,r},{mx,mn}}]; else mp[p]=mp[{{l,r-1},{mx,mn}}]; } void solve(){ cin>>n; double p=0; s=0; for(int i=0;i<n;i++){ cin>>a[i]; s+=a[i]; } p=s;s/=n; sol(0,n-1,s,s,p); ld ans=1000000008.0; for(auto i:mp) if(i._1._1._1==0&&i._1._1._2==n-1) ans=min(ans,i._2); cout<<fixed<<setprecision(10); cout<<ans<<endl; } intt main() { FFF //freopen("fcolor.in", "r", stdin); //freopen("fcolor.out", "w", stdout); tst = 1; //cin >> tst; for ( ts = 1; ts <= tst; ts++ ){ solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...