Nhận xét 1: Để tối ưu thì Jessie luôn di chuyển theo thứ tự từ ngôi nhà có thứ tự nhỏ đến ngôi nhà có thứ tự lớn hơn.

Nhận xét 2: Nếu ta biết trước chuyến đi của Jessie bắt đầu từ ngôi nhà $s$ và kết thúc ở ngôi nhà $t$, thì tổng độ yêu thích tối đa, kí hiệu là $F(s,t)$ sẽ được xác định bằng công thức:

Nói cách khác, do khoảng cách di chuyển là cố định, nên độ hài lòng tối đa sẽ phụ thuộc vào độ yêu thích tối đa, và có thể được xác định một cách tham lam bằng cách xác định ngôi nhà có độ yêu thích cao nhất trong đoạn $[s,t]$ từng món quà.

Như vậy ta có thể dễ dàng giải được bài toán với độ phức tạp $𝒪(N^{3}M)$ với chi phí tìm ~\max C_{ij}~ là $𝒪(N)$. Ta có thể dùng bảng thưa để tối ưu chi phí thành $𝒪(1)$ và độ phức tạp thành $𝒪(N^{2}M)$, tương ứng với 4 subtask đầu tiên của đề bài.

Gọi $dp[i]$ là độ hài lòng tối ưu nếu Jessie kết thúc hành trình tại ngôi nhà thứ $i$, ta có:

với $D(j,i)$ là tổng chi phí di chuyển từ nhà $j$ đến nhà $i$.

Gọi $opt[i]$ là vị trí $j$ tối ưu cho $dp[i]$. Ta nhận thấy rằng

Vì nếu $opt[i]>opt[i+1]$ thì luôn tồn tại cách tối ưu hơn bằng cách Jessie xuất phát từ $opt[i]$.

Từ nhận xét này, ta có thể áp dụng kĩ thuật chia để trị để tối ưu hóa chi phí chuyển quy hoạch động từ $O(N)$ thành $O(\log N)$. Và độ phức tạp của thuật toán là $𝒪(N\log NM)$

int n, m;
const int N = 5005, M = 205, LOG = 13;
ll d[N];
ll c[N][M];
ll dp[N];
ll table[M][N][LOG];
ll prefix[N];
const ll INF = 1e18;

void Input() {
    cin >> n >> m;
    reu(i, 1, n-1) cin >> d[i];
    reu(i, 1, n) reu(j, 1, m) cin >> c[i][j];
}

ll query(int x, int L, int R) {
    int k = __lg(R-L+1);
    return max(table[x][L][k], table[x][R - MASK(k) + 1][k]);
}

ll calc(int L, int R) {
    ll ans = 0;
    reu(x, 1, m) ans += query(x, L, R);
    return ans - prefix[R-1] + (L ? prefix[L-1] : 0);
}

void DP(int L, int R, int optL, int optR) {
    if (L > R) return;
    int mid = (L+R) >> 1;
    ll best = -INF;
    int optM = -1;
    reu(i, optL, min(optR, mid)) {
        if (maximize(best, calc(i, mid))) optM = i;
    }
    dp[mid] = best;
    DP(L, mid-1, optL, optM);
    DP(mid+1, R, optM, optR);
}

void Solve() {
    reu(i, 1, n) prefix[i] = prefix[i-1] + d[i];

    //build table
    reu(i, 1, n) reu(x, 1, m) table[x][i][0] = c[i][x];
    reu(x, 1, m) reu(k, 1, LOG-1)
        for(int i = 1; i + MASK(k) - 1 <= n; ++i) {
            table[x][i][k] = max(table[x][i][k-1], table[x][i + MASK(k-1)][k-1]);
        }

    reu(i, 1, n) dp[i] = c[i][1];
    DP(1, n, 1, n);
    ll ans = 0;
    reu(i, 1, n) maximize(ans, dp[i]);
    cout << ans;
}