rt

我拿一个 $O(nmp)$ 的 dp 去递交 AC 了，如果这道题上极限数据的话会爆掉。

AC 记录。

原代码：

// #pragma GCC optimize(2) // 开启O2优化
#include<bits/stdc++.h>
using namespace std;
#define N 2010
#define INF 0x3f3f3f3f // 无穷大
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define func function<void()>
// 先考虑一个 O(nmp) 的转移
ll dp[N][N];// 表示当前时间为 i 位置为 j
ll maxn[N];
ll a[N][N];
ll v[N];
int n,m,p,ki,kj;
ll sum,ans;

// 输入函数
void input(){
    scanf("%d%d%d",&n,&m,&p);
    for(int i = 1;i <= m;++i)memset(dp[i],-0x3f,sizeof(dp[i]));
    memset(maxn,-0x3f,sizeof(maxn));
    maxn[m+1] = 0;
    for(int i = 1;i <= n;++i){
        for(int j = 1;j <= m;++j)scanf("%lld",a[j] + i);
    }
    for(int i = 1;i <= n;++i)scanf("%lld",v+i);
}

// 处理函数
void solve(){
    for(int i = m;i >= 1;--i){
        for(int j = 1;j <= n;++j){
            kj = j;
            sum = 0;
            for(int k = 1;k <= p;++k){
                if(i + k > m + 1)break;// 不能超过
                sum += a[i + k - 1][kj];
                if(kj == n)kj = 1;
                else ++kj;
                dp[i][j] = max(dp[i][j],maxn[i+k] + sum - v[j]);
            }
            maxn[i] = max(maxn[i],dp[i][j]);
        }
    }
}

// 输出函数
void output(){
//    for(int i = 1;i <= n;++i)ans = max(ans,dp[1][i]);
    printf("%lld",maxn[1]);
}

// 主函数
int main(int argc,char* argv[]){
	input();
	solve();
	output();
	return 0;
}