老师的正解是错的，时间复杂度是O(NNM)最大是5*10^8

我的新的题解优化了一下将一个N优化成了K O(NMK)最大为2.5*10^7主要使用了一个类似前缀dp的高级做法，只能说老师还是太菜了，菜就要多练建议拜我为师

这个数据用时我100ms 老师600ms 但是数据有点水 其实是能卡掉老师的代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define lowbit(x) x&-x
#define ull unsigned long long
#define ls(x) x<<1
#define rs(x) x<<1|1
const int INF = 0x3f3f3f3f3f3f3f3f;
const int N = 1e3+10;
const int M = 1e5 + 10;
const int K = 1e5 + 10;
const int mod = 10007;
const int base = 998244353;
int n,m,k;
int a[N][N];
int pre[N][N];
int sum[N][N];
int sum1[N][N];
int dp[N][N];
int ans;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	freopen("shop.in","r",stdin);
	freopen("shop.out","w",stdout);
	cin>>n>>m>>k;
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++){
			cin>>a[i][j];
			pre[i][j]=pre[i][j-1]+a[i][j];
		}
	}
	for(int j=1;j+k-1<=n;j++){
		dp[1][j]=pre[1][j+k-1]-pre[1][j-1];
	}
	for(int j=1;j+k-1<=n;j++){
		sum[1][j]=max(sum[1][j-1],dp[1][j]+pre[2][j+k-1]-pre[2][j-1]);//前缀dp
	}
	for(int j=n-k+1;j>=1;j--){
		sum1[1][j]=max(sum1[1][j+1],dp[1][j]+pre[2][j+k-1]-pre[2][j-1]);//后缀dp
	}
	for(int i=2;i<=m;i++){
		for(int j=1;j+k-1<=n;j++){
			if(j-k>=1){
				dp[i][j]=max(sum[i-1][j-k]+pre[i][j+k-1]-pre[i][j-1],dp[i][j]);
			}
			for(int s=max(1ll,j-k+1);s<=min(n-k+1,j+k-1);s++){
				dp[i][j]=max(dp[i][j],dp[i-1][s]+pre[i][s+k-1]-pre[i][s-1]+pre[i][j+k-1]-pre[i][j-1]-(pre[i][min(s+k-1,j+k-1)]-pre[i][max(s,j)-1]));
			}
			if(j+k<=n-k+1){
				dp[i][j]=max(dp[i][j],sum1[i-1][j+k]+pre[i][j+k-1]-pre[i][j-1]);
			}
			sum[i][j]=max(sum[i][j-1],dp[i][j]+pre[i+1][j+k-1]-pre[i+1][j-1]);//前缀dp
		}
		for(int j=n-k+1;j>=1;j--){
			sum1[i][j]=max(sum1[i][j+1],dp[i][j]+pre[i+1][j+k-1]-pre[i+1][j-1]);//后缀dp
		}
	}
	for(int i=1;i<=n-k+1;i++){
		ans=max(ans,dp[m][i]);
	}
	cout<<ans;
	return 0;
}
/*
显然这是一个dp
我们定义dp[i][j]表示第i天，补货的是从j开始j+k-1结束能赚到的东西的
*/