题解

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAXN = 1005;
const int MAXM = 1005;
const int NEG = -1000000000;

int coin[MAXN][MAXM];
int cost[MAXN];
int dp[MAXM];
int pre[MAXN];
int q_s[MAXN][MAXM];
int q_val[MAXN][MAXM];
int head[MAXN], tail[MAXN];

int main() {
int n, m, p;
scanf("%d %d %d", &n, &m, &p);
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
scanf("%d", &coin[i][j]);
for (int i = 0; i < n; i++)
scanf("%d", &cost[i]);

for (int t = 0; t <= m; t++) dp[t] = NEG;
dp[0] = 0;

for (int u = 0; u < n; u++) {
    head[u] = 0;
    tail[u] = 0;
    pre[u] = 0;
}

for (int t = 1; t <= m; t++) {
    for (int u = 0; u < n; u++) {
        int i = (u + t - 1) % n;
        if (dp[t-1] != NEG) {
            int val = dp[t-1] - pre[u] - cost[i];
            while (head[u] < tail[u] && q_val[u][tail[u]-1] <= val) {
                tail[u]--;
            }
            q_s[u][tail[u]] = t-1;
            q_val[u][tail[u]] = val;
            tail[u]++;
        }
        pre[u] += coin[i][t-1];
        while (head[u] < tail[u] && q_s[u][head[u]] < t - p) {
            head[u]++;
        }
        if (head[u] < tail[u]) {
            int cand = pre[u] + q_val[u][head[u]];
            if (cand > dp[t]) dp[t] = cand;
        }
    }
}

printf("%d\n", dp[m]);
return 0;

}