求调
查看原帖
求调
304458
ZHUHK楼主2022/10/29 13:35
#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N=6e3+10;
LL a[N];
int q[N][N],hh[N],tt[N],m,k,n;
LL f[N][N];
int main(){
	scanf("%d%d%d",&n,&k,&m);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
	
	fill(tt+1,tt+1+m,-1);
	tt[0]=0;
	if(n/k>m) {
		puts("-1");return 0;
	}
	for(int i=1;i<=n;i++){
		for(int j=m;j>=1;j--){
			while(hh[j-1]<=tt[j-1]&&q[hh[j-1]][j-1]<i-k) hh[j-1]++;
			f[i][j]=f[q[hh[j-1]][j-1]][j-1]+a[i];
			while(f[q[tt[j]][j]][j]<=f[i][j]&&hh[j]<=tt[j]) tt[j]--;
			q[++tt[j]][j]=i;
		}
	}
	LL ans=-0x3f3f3f3f;
	for(int i=n-k+1;i<=n;i++)ans=max(ans,f[i][m]);
	cout<<ans<<endl;
	return 0;
}
2022/10/29 13:35
加载中...