claude-soneet-4.6

#include <bits/stdc++.h>
using namespace std;

// a[i][j]: 第i条路(0-indexed)，第j时刻(1-indexed)的金币数
// pre[i][j]: 斜线前缀和，表示沿"路i时刻j, 路i-1时刻j-1, ..."方向的累计
//   即 pre[i][j] = a[i][j] + pre[(i-1+n)%n][j-1]
// 意义：机器人在时刻j走到路i，此前连续走的金币（包括当前步）
//
// dp[j]: 经过前j个时刻，最大净金币数
// 转移：在时刻 j-k+1 购买机器人（从工厂s出发），走k步，到时刻j结束
//   最终在路 e = (s + k - 1) % n，出发路 s = (e - k + 1 + n) % n
//   收集金币 = pre[e][j] - pre[(e-k+n)%n][j-k]  (前缀差)
//   购买费用 = cost[s] = cost[(e-k+1+n)%n]
//   dp[j] = max over k,e { dp[j-k] - cost[(e-k+1+n)%n] + pre[e][j] - pre[(e-k+n)%n][j-k] }
//
// 对固定k，枚举e（0..n-1）和使用dp[j-k]:
//   dp[j] = max_e { (pre[e][j]) + max_{e} { dp[j-k] - cost[(e-k+1+n)%n] - pre[(e-k+n)%n][j-k] } }
// 令 t = (e-k+n)%n  (即 t = e-k mod n, t 与 e 一一对应)
//   inner = dp[j-k] - cost[(t+1)%n] - pre[t][j-k]
//   outer = pre[(t+k)%n][j]
//   dp[j] = max over k,t { inner(t, j-k) + pre[(t+k)%n][j] }
//
// 对固定k，在时刻j-k时，对每个t预计算 val[t] = dp[j-k] - cost[(t+1)%n] - pre[t][j-k]
// 然后 dp[j] = max over k { max_t { val[t] + pre[(t+k)%n][j] } }
// 但t和(t+k)%n是绑定的，枚举e = (t+k)%n => t=(e-k+n)%n
// 所以对固定k: dp[j] = max_e { pre[e][j] + f[k][(e-k+n)%n] }
// 其中 f[k][t] = dp[j-k] - cost[(t+1)%n] - pre[t][j-k]  (这个值在确定j-k后才能算)
//
// 实现：外层枚举j，内层枚举k，内内层枚举e（即枚举终点路）

const int MAXN = 1005;
const int MAXM = 1005;
const long long NEG_INF = -1e18;

int n, m, p;
long long a[MAXN][MAXM];    // a[i][j]: 路i(0-indexed), 时刻j(1-indexed)
long long cost[MAXN];       // cost[i]: 工厂i(0-indexed)购买机器人的费用
long long pre[MAXN][MAXM];  // 斜线前缀和
long long dp[MAXM];         // dp[j]

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> p;

    for(int i = 0; i < n; i++)
        for(int j = 1; j <= m; j++)
            cin >> a[i][j];

    for(int i = 0; i < n; i++)
        cin >> cost[i];

    // 计算斜线前缀和
    // pre[i][j] = a[i][j] + pre[(i-1+n)%n][j-1]
    // 表示机器人走到"路i，时刻j"这一步时，从某处出发连续走的金币总和（向前追溯）
    // 初始化 pre[i][0] = 0
    for(int i = 0; i < n; i++) pre[i][0] = 0;
    for(int j = 1; j <= m; j++)
        for(int i = 0; i < n; i++)
            pre[i][j] = a[i][j] + pre[(i-1+n)%n][j-1];

    // dp初始化
    // dp[0] = 0 (还没开始)
    // dp[j] = NEG_INF 初始（未计算）
    for(int j = 0; j <= m; j++) dp[j] = NEG_INF;
    dp[0] = 0;

    for(int j = 1; j <= m; j++){
        // 枚举步数 k (1 <= k <= min(p, j))
        int klim = min(p, j);
        for(int k = 1; k <= klim; k++){
            int prev = j - k; // 上一机器人消失时刻
            if(dp[prev] == NEG_INF) continue;
            // 枚举终点路 e (0-indexed)
            // 出发路(工厂) s = (e - k + 1 + n*k) % n  即 (e - k + 1) mod n
            // 等价：出发工厂 s，终点路 e = (s + k - 1) % n
            // 收集金币 = pre[e][j] - pre[(e-k+n)%n][prev]
            //   注意(e-k+n*...)%n可能需要多加几个n，用 ((e-k)%n+n)%n
            // 购买费用 = cost[s] = cost[((e - k + 1) % n + n) % n]
            for(int e = 0; e < n; e++){
                int t = ((e - k) % n + n) % n;  // t = (e-k+n)%n, 前一步的路
                int s = (t + 1) % n;             // 出发工厂
                long long coins = pre[e][j] - pre[t][prev];
                long long val = dp[prev] - cost[s] + coins;
                if(val > dp[j]) dp[j] = val;
            }
        }
    }

    // 答案：dp[1..m]中的最大值
    // 注意：游戏必须进行m个时刻，但机器人可以在m之前结束（不一定要走满m步）
    // 实际上题目要求"经过m个单位时间后"，机器人可以在中途消失后再买新的
    // dp[j]表示前j时刻结束后的最大净金币，答案取 dp[m] 即可
    // 但注意：如果m时刻之前机器人就走完了且没买新的，那些时刻没有收集金币
    // 题目说"当马路上的机器人行走完规定的次数之后会自动消失，小新必须立刻购买新的"
    // 所以必须始终有机器人，dp[m]就是答案（必须走完所有m步）

    cout << dp[m] << endl;

    return 0;
}