D. Keep the Average High

https://codeforces.com/problemset/problem/1616/D
great question!
题解：首先我们令a[i]-=x,这样条件变成了区间和>=0.由裴蜀定理，n可以分解为2x+3y。
我们提出以下命题：对于a中任意子串之和>=0等价于任意长度为2或3的子串和>=0。
充分性显然。对于必要性，对任意长度大于3的子串，可分解为若干2子串和3子串，其和>=0故总体和>=0得证。
故我们可以dp,令f[i][0/1][0/1]表示前i个元素，i-1位不选/选，i位不选/选，则可O(1)转移，总复杂度位O(n),转移方程见代码。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e4+100;
int a[N],f[N][2][2];
void solve(){
	int n;cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	int x;cin>>x;
	for(int i=1;i<=n;i++) a[i]-=x;
	a[0]=0;
	f[1][0][1]=1,f[1][0][0]=0,f[1][1][0]=0,f[1][1][1]=1;
	for(int i=2;i<=n;i++){
		f[i][0][0]=max(f[i-1][0][0],f[i-1][1][0]);
		f[i][1][0]=max(f[i-1][0][1],f[i-1][1][1]);
		f[i][0][1]=max(f[i-1][0][0],f[i-1][1][0])+1;
		if(a[i]+a[i-1]<0) f[i][1][1]=-1;
		else{
			f[i][1][1]=f[i-1][0][1]+1;
			if(a[i-2]+a[i-1]+a[i]>=0){
				f[i][1][1]=max(f[i][1][1],f[i-1][1][1]+1);
			}
		}
		
	}
	int ans=max({f[n][0][0],f[n][0][1],f[n][1][0],f[n][1][1]});
		cout<<ans<<endl;
}
signed main(){
	int T;cin>>T;
	while(T--) solve();
}