บ่อน้ำมันสามผืน: เลิกเลือกบล็อก แล้วหันไปเลือกเส้นที่แบ่งกระดาน

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int M, N, K, MB, NB;
vector<int> pre, blk, f1, f2, f3, f4;
inline int P(int i, int j){ return pre[(size_t)i * (N + 1) + j]; }
inline int&BK(int i, int j){ return blk[(size_t)i * (NB + 2) + j]; }   // มุมบนซ้ายที่ (i, j) ฐานหนึ่ง
inline int&F1(int i, int j){ return f1[(size_t)i * (NB + 2) + j]; }
inline int&F2(int i, int j){ return f2[(size_t)i * (NB + 2) + j]; }
inline int&F3(int i, int j){ return f3[(size_t)i * (NB + 2) + j]; }
inline int&F4(int i, int j){ return f4[(size_t)i * (NB + 2) + j]; }

int main(){
    if(scanf("%d %d %d", &M, &N, &K) != 3) return 0;
    pre.assign((size_t)(M + 1) * (N + 1), 0);
    for(int i = 1; i <= M; i++) for(int j = 1; j <= N; j++){ int x; scanf("%d", &x);
        pre[(size_t)i * (N + 1) + j] = x + P(i-1, j) + P(i, j-1) - P(i-1, j-1); }

    MB = M - K + 1; NB = N - K + 1;
    blk.assign((size_t)(MB + 2) * (NB + 2), 0);
    for(int i = 1; i <= MB; i++) for(int j = 1; j <= NB; j++)
        BK(i, j) = P(i+K-1, j+K-1) - P(i-1, j+K-1) - P(i+K-1, j-1) + P(i-1, j-1);

    // ตารางมุมสี่ทิศ ค่าที่ดีที่สุดของบล็อกที่อยู่ในสี่เหลี่ยมมุมนั้นทั้งก้อน
    f1.assign(blk.size(), 0); f2.assign(blk.size(), 0); f3.assign(blk.size(), 0); f4.assign(blk.size(), 0);
    for(int i = 1; i <= MB; i++) for(int j = 1; j <= NB; j++) F1(i,j) = max(BK(i,j), max(F1(i-1,j), F1(i,j-1)));
    for(int i = 1; i <= MB; i++) for(int j = NB; j >= 1; j--) F2(i,j) = max(BK(i,j), max(F2(i-1,j), F2(i,j+1)));
    for(int i = MB; i >= 1; i--) for(int j = 1; j <= NB; j++) F3(i,j) = max(BK(i,j), max(F3(i+1,j), F3(i,j-1)));
    for(int i = MB; i >= 1; i--) for(int j = NB; j >= 1; j--) F4(i,j) = max(BK(i,j), max(F4(i+1,j), F4(i,j+1)));

    // ค่าที่ดีที่สุดของบล็อกที่แถวบนเป็น i พอดี และที่คอลัมน์ซ้ายเป็น j พอดี
    vector<int> rb(MB + 2, 0), cb(NB + 2, 0);
    for(int i = 1; i <= MB; i++) for(int j = 1; j <= NB; j++){ rb[i] = max(rb[i], BK(i,j)); cb[j] = max(cb[j], BK(i,j)); }
    vector<int> rp(MB + 2, 0), rs(MB + 3, 0), cp(NB + 2, 0), cs(NB + 3, 0);
    for(int i = 1; i <= MB; i++) rp[i] = max(rp[i-1], rb[i]);
    for(int i = MB; i >= 1; i--) rs[i] = max(rs[i+1], rb[i]);
    for(int j = 1; j <= NB; j++) cp[j] = max(cp[j-1], cb[j]);
    for(int j = NB; j >= 1; j--) cs[j] = max(cs[j+1], cb[j]);
    auto A  = [&](int t){ int k = t - K + 1; return (k >= 1) ? rp[min(k, MB)] : 0; };   // ดีที่สุดในแถว 1..t
    auto Bv = [&](int t){ return (t <= MB) ? rs[max(t, 1)] : 0; };                      // ดีที่สุดในแถว t..M
    auto L  = [&](int v){ int k = v - K + 1; return (k >= 1) ? cp[min(k, NB)] : 0; };
    auto Rv = [&](int v){ return (v <= NB) ? cs[max(v, 1)] : 0; };

    ll best = 0;
    // 1. แถบแนวนอนสามแถบ เดินตามแถบกลางที่มีแถวบนเป็น m
    for(int m = 1; m <= MB; m++) best = max(best, (ll)A(m-1) + rb[m] + Bv(m + K));
    // 2. แถบแนวตั้งสามแถบ
    for(int m = 1; m <= NB; m++) best = max(best, (ll)L(m-1) + cb[m] + Rv(m + K));
    // 3. ตัดขวางที่ t ครึ่งบนหนึ่งบล็อก ครึ่งล่างตัดตั้ง
    for(int t = K; t + K <= M; t++){ int bi = t + 1, inner = 0;
        for(int v = K; v + K <= N; v++) inner = max(inner, F3(bi, v-K+1) + F4(bi, v+1));
        best = max(best, (ll)A(t) + inner); }
    // 4. ตัดขวางที่ t ครึ่งล่างหนึ่งบล็อก ครึ่งบนตัดตั้ง  (t เริ่มที่ K ไม่ใช่ 2K)
    for(int t = K; t <= M - K; t++){ int inner = 0;
        for(int v = K; v + K <= N; v++) inner = max(inner, F1(t-K+1, v-K+1) + F2(t-K+1, v+1));
        best = max(best, (ll)Bv(t+1) + inner); }
    // 5. ตัดตั้งที่ v ครึ่งซ้ายหนึ่งบล็อก ครึ่งขวาตัดขวาง
    for(int v = K; v + K <= N; v++){ int bj = v + 1, inner = 0;
        for(int t = K; t + K <= M; t++) inner = max(inner, F2(t-K+1, bj) + F4(t+1, bj));
        best = max(best, (ll)L(v) + inner); }
    // 6. ตัดตั้งที่ v ครึ่งขวาหนึ่งบล็อก ครึ่งซ้ายตัดขวาง
    for(int v = K; v <= N - K; v++){ int inner = 0;
        for(int t = K; t + K <= M; t++) inner = max(inner, F1(t-K+1, v-K+1) + F3(t+1, v-K+1));
        best = max(best, (ll)Rv(v+1) + inner); }
    printf("%lld\n", best);
}

// ตัวตรวจ ลองทุกสามบล็อกที่ไม่ทับกัน ไม่มีทฤษฎีการแบ่งแถบอยู่ในนี้เลย
#include <bits/stdc++.h>
using namespace std;
int M, N, K; int g[20][20];
int blockSum(int r, int c){ int s = 0;
    for(int i = 0; i < K; i++) for(int j = 0; j < K; j++) s += g[r+i][c+j]; return s; }
bool ov(int r1, int c1, int r2, int c2){
    return !(r1 + K <= r2 || r2 + K <= r1 || c1 + K <= c2 || c2 + K <= c1); }
int main(){
    scanf("%d %d %d", &M, &N, &K);
    for(int i = 0; i < M; i++) for(int j = 0; j < N; j++) scanf("%d", &g[i][j]);
    vector<array<int,3>> P;
    for(int r = 0; r + K <= M; r++) for(int c = 0; c + K <= N; c++) P.push_back({r, c, blockSum(r, c)});
    long long best = -1;
    for(size_t a = 0; a < P.size(); a++) for(size_t b = a + 1; b < P.size(); b++){
        if(ov(P[a][0], P[a][1], P[b][0], P[b][1])) continue;
        for(size_t c = b + 1; c < P.size(); c++){
            if(ov(P[a][0], P[a][1], P[c][0], P[c][1]) || ov(P[b][0], P[b][1], P[c][0], P[c][1])) continue;
            best = max(best, (long long)P[a][2] + P[b][2] + P[c][2]); } }
    printf("%lld\n", best);
}

// รุ่นที่ผิด ทรงที่ 4 กับ 6 เริ่มเส้นตัดที่ 2K ทั้งที่ควรเริ่มที่ K
for(int t = 2 * K; t <= M - K; t++){ ... }     // ครึ่งบนวางสองบล็อกเรียงกันแนวนอน
for(int v = 2 * K; v <= N - K; v++){ ... }     // ครึ่งซ้ายวางสองบล็อกเรียงกันแนวตั้ง