Submission #28761328

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
template <class T>
inline T read(){
    T r=0,f=0;char c=getchar();
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) r=(r<<3)+(r<<1)+(c^48),c=getchar();
    return f?-r:r;
}
const int N=1e5+5,INF=1e9;
int n,a[N];
const double eps=1e-5;
bool check(double mid){
    double f[N];
    f[1]=a[1]-mid;
    for(int i=2;i<=n;++i) f[i]=-INF;
    for(int i=2;i<=n;++i) f[i]=max(f[i-1]+a[i]-mid,f[i-2]+a[i]-mid);
    return f[n]>0||f[n-1]>0;
}
bool check(int mid){
    int del=0,cntmax=0,cntmin=0;
    for(int i=1;i<=n;++i){
        if(a[i]<mid){
            if(del+1==i) continue;
            del=i,++cntmin;
        }
        else del=i,++cntmax;
    }
    return cntmin<cntmax;
}
int main(){
    n=read<int>();
    for(int i=1;i<=n;++i) a[i]=read<int>();
    double l1=0,r1=1e9,ans1;
    while(r1-l1>eps){
        double mid=(l1+r1)/2;
        if(check(mid)) ans1=mid,l1=mid;
        else r1=mid;
    }
    int l=0,r=1e9,ans2;
    while(l<=r){
        int mid=l+r>>1;
        if(check(mid)) ans2=mid,l=mid+1;
        else r=mid-1;
    }
    printf("%lf\n%d",ans1,ans2);
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:42:18: warning: suggest parentheses around ‘+’ inside ‘>>’ [-Wparentheses]
   42 |         int mid=l+r>>1;
      |                 ~^~

Judge Result