题解 | 牛牛与切割机

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

using ll=long long;
using ull=unsigned long long;
using i128=__int128_t;
using u128=__uint128_t;
using ld=long double;

void solve()
{
	ll n,sum=0,MIN=1e6,MAX=-1e6;//设一部分的值为x 那另外一部分即n-x 代价即x(n-x)
	cin >> n;// 这是一个二次函数 求导易x=n/2时取最大值 所以我们找到x的最大值和最小值 判断哪个离n/2最远即可
	vector<ll>v(n+1,0),pre(n+1,0);
	for(int i=1;i<=n;i++)
	{
		cin >> v[i];
		sum+=v[i];
		pre[i]=pre[i-1]+v[i];
		MIN=min(MIN,pre[i]);
		MAX=max(MAX,pre[i]);
	}
	if(sum==MAX) MAX-=v[n];//注意 最大值可能和全部元素的和相等 这样会导致划分出空序列 如果时这样的情况 我们需要将最大值转化为次大值
	int a=sum/2-MIN,b=MAX-sum/2;
	if(a>=b) cout << MIN*(sum-MIN);
	else cout << MAX*(sum-MAX);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int t=1;
	//cin >> t;
	
	while(t--)
	{
		solve();
	}
	return 0;
}