求助:为何RE/kel
查看原帖
求助:为何RE/kel
160839
Prean楼主2020/11/6 13:17

RE on 2,本地搞了几组数据并没有炸掉,求 dalao 解释/kel

#include<cstdio>
typedef long long ll;
const int M=5005;
int n,m,k,L,R,q[M],a[M];
ll ans,v[M],dp[M];
inline ll max(const ll&a,const ll&b){
	return a>b?a:b;
}
signed main(){
	register int i;register ll val;
	scanf("%d%d%d",&n,&k,&m);if(k*(m+1)-1<n)return!putchar(45),putchar(49);
	for(i=1;i<=n;++i)scanf("%d",a+i);
	while(m--){
		L=1;R=0;q[1]=v[1]=0;
		for(i=1;i<=n;++i){
			if(q[L]+k<i)++L;
			val=dp[i];
			dp[i]=v[L]+a[i];
			while(L<=R&&val>=v[R])--R;
			++R;q[R]=i;v[R]=val;
		}
	}
	for(i=n-k+1;i<=n;++i)ans=max(ans,dp[i]);
	printf("%lld",ans);
}
2020/11/6 13:17
加载中...