Submission #1157179

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157179		alexander707070	Seesaw (JOI22_seesaw)	C++20	34 / 100	271 ms	872 KiB

seesaw

#include<bits/stdc++.h>
#define MAXN 107
using namespace std;

int n,a[MAXN];
long double pref[MAXN];
vector<long double> w;

long double dp[MAXN][MAXN],curr,ans;
int li[MAXN][MAXN],tim;

long double av(int l,int r){
	return (pref[r]-pref[l-1])/(r-l+1);
}

const int inf=1e9;

long double ff(int l,int r){
	if(l==r)return a[l];

	if(li[l][r]==tim)return dp[l][r];
	li[l][r]=tim;
	dp[l][r]=inf;

	if(av(l,r-1)>=curr)dp[l][r]=min(dp[l][r],max(av(l,r),ff(l,r-1)));
	if(av(l+1,r)>=curr)dp[l][r]=min(dp[l][r],max(av(l,r),ff(l+1,r)));

	return dp[l][r];
}

int main(){

	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin>>n;

	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++)pref[i]=pref[i-1]+a[i];

	for(int i=1;i<=n;i++){
		for(int f=i;f<=n;f++){
			w.push_back(av(i,f));
		}
	}

	sort(w.begin(),w.end());

	ans=inf;
	for(int i=0;i<w.size();i++){
		tim++;
		curr=w[i];

		if(av(1,n)<w[i])break;
		ans=min(ans,ff(1,n)-w[i]);
	}

	cout<<setprecision(10)<<fixed<<ans<<"\n";

	return 0;
}

• Subtask 1: 1 / 1
• Subtask 2: 33 / 33
• Subtask 3: 0 / 33
• Subtask 4: 0 / 33