C++(clang++ 11.0.1) 解法, 执行用时: 61ms, 内存消耗: 4304K, 提交时间: 2022-11-24 11:25:00

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 5;
int n,ans,a[N],b[N],s[N],f[N][2];
signed main(){
	cin>>n;
	for(int i=1;i<=n;++i){
		cin>>a[i];
		s[i] = s[i-1] + a[i];
		f[i][0] = f[i-1][0];
		f[i][1] = f[i-1][1];
		f[i][s[i]&1]++;
	}
	for(int i=n;i>=1;--i) b[i] = max(b[i+1],a[i]);
	int tot = 0;
	for(int i=1;i<=n;++i){
		int mx=0;
		for(int j=i;j<=n;++j){
			mx = max(mx,a[j]);
			if(s[j]-s[i-1]>=b[i]*2){
				ans += f[n][s[i-1]&1] - f[j-1][s[i-1]&1];
				break;
			}
			if(s[j]%2==s[i-1]%2&&(s[j]-s[i-1])>=mx*2) ans++;		
		}
	}
	cout<<ans<<endl;
	return 0;
}