P8102

挺冷门的单调队列但是有如下逆天代码请各位鉴赏

#include<bits/stdc++.h>
#define N 1e6+10
using namespace std;
bool cmp(int a,int b){
	return a > b;
}
int n,m,A,arr[5000005];
int q[5000005],err[5000005],ans=-1;
int main(){
	cin>>n;
	
	if(n>500){//注意看这一段
		cin>>m>>A;
		for(int i=1;i<=n;i++){
			cin>>arr[i];
		}
		sort(arr+1,arr+n+1,cmp);
		int cnt = 0,ans = 0;
		int ccc = 1;
		while(cnt <= n-m+1){
			for(int i = 1;i <= m;i++){
				if(!(cnt <= n-m+1)) break;
				ans += arr[ccc];
				cnt++;
			}
			ccc++;
		}
		cout << ans;
		return 0;
	}
	else{
		cin>>m>>A;
		for(int i=1;i<=n;i++){
			cin>>arr[i];
		}
		for(int i=1;i<=n-m+1;i++){
			int maxn=0;
			for(int j=i;j<=i+m-1;j++){
				maxn=max(arr[j],maxn);
			}
			q[i]=maxn;
			err[i]=err[i-1]+q[i];
		}
		int firs=A;
		for(int i=1;i<=m-2;i++){
			firs=max(firs,arr[i]);
		}
		ans=firs+err[n-m+1];
		for(int i=1;i<=m;i++){
			int now=0;
			for(int j=1;j<=i;j++){
				int maxn=A;
				for(int k=j;k<=j+m-2;k++){
					maxn=max(arr[k],maxn);
				}
				now+=maxn;
			}
			ans=max(ans,now+err[n-m+1]-err[i-1]);
		}
		for(int i=m;i<=n-m+1;i++){
			int now=0;
			for(int j=i-m+1;j<=i;j++){
				int maxn=A;
				for(int k=j;k<=j+m-2;k++){
					maxn=max(arr[k],maxn);
				}
				now+=maxn;
			}
			int maxn=A;
			for(int j=i;j<=i+m-1;j++){
				maxn=max(maxn,arr[j]);
			}
		//now-=maxn;
			ans=max(ans,now+err[n-m+1]-err[i-1]+err[i-m]);
		}
		int aa=A;
		for(int i=n-m+2;i<=n;i++){
			aa=max(aa,arr[i]);
		}
		ans=max(ans,aa+err[n-m+1]);
	
		cout<<ans;
		return 0;
	}
}

原理：第一个点暴力，别的排序（绷）