Cá nhân mình thấy bài này thuật toán không có gì khó, tuy nhiên để cài đặt chính xác trong thời gian hạn hẹp thì không đơn giản.

Bài này sử dụng kỹ thuật mảng cộng dồn 2D để có thể truy vấn nhanh tổng của một hình chữ nhật trong ~O(1)~. Để tính nhanh tổng của một hình thoi thì ta quay bảng một góc ~45~ độ (nhìn theo đường chéo), và hình thoi sẽ trở thành hình chữ nhật.

Bước tiếp theo là ta sẽ for các đường cắt của hai hình (vì hai hình rời nhau nên sẽ tồn tại đường thẳng mà hai hình nằm trên hai nửa mặt phẳng). Các đường cắt cần thiết có thể nằm ngang, nằm dọc, hoặc xiên góc ~45~ độ. Ta sẽ giải quyết trường hợp đường cắt nằm ngang, trong đó hình chữ nhật ở trên, còn hình thoi ở dưới, các trường hợp khác tương tự: Tạo mảng ~Up[], Down[]~ trong đó ~Up[i]~ là hình chữ nhật có tổng lớn nhất nằm gọn trong khoảng từ hàng ~1~ đến hàng ~I~, tương tự ~Down[i]~ là hình thoi max gọn trong khoảng hàng ~i~ đến hàng ~m~. Kết quả của trường hợp này sẽ là ~max(Up[i]~ ~+~ ~Down[i + 1])~.

Để code được gọn thì ta chỉ cần giải quyết một số trường hợp cơ sở, rồi lần lượt quay bảng ~90~ độ và sử dụng lại code.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của ladpro98

#include <bits/stdc++.h>

using namespace std;

const int N = 2016;
const long long INF = (long long)1e18;

long long a[N][N];
long long b[N][N];
long long diamond[N][N];
long long sa[N][N];
long long sb[N][N];

void buildS(long long a[][N], long long s[N][N], int m, int n) {
    for (int i = 1; i <= m; ++i) for (int j = 1; j <= n; ++j)
        s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
}

long long getSum(long long s[][N], int x, int y, int u, int v) {
    return s[u][v] - s[u][y - 1] - s[x - 1][v] + s[x - 1][y - 1];
}

int n, m, A, B, K, mn;
long long ans;
long long up[N];
long long down[N];

void maximize(long long &a, long long b) {
    a = a < b ? b : a;
}

void solveLine() {
    for (int i = 0; i <= m; ++i) up[i] = -INF;
    for (int i = A; i <= m; ++i) for (int j = B; j <= n; ++j)
        maximize(up[i], getSum(sa, i - A + 1, j - B + 1, i, j));
    for (int i = 1; i <= m; ++i) maximize(up[i], up[i - 1]);
    for (int i = 0; i <= m; ++i) down[i] = -INF;
    for (int i = K + 1; i + K <= m; ++i) for (int j = K + 1; j + K <= n; ++j)
        maximize(down[i - K], diamond[i][j]);
    for (int i = m - 1; i >= 1; --i) maximize(down[i], down[i + 1]);
    for (int i = A; i < m; ++i) maximize(ans, up[i] + down[i + 1]);
}

void solveDiag() {
    for (int i = 0; i <= mn + 1; ++i) up[i] = down[i] = -INF;
    for (int i = A; i <= m; ++i) for (int j = B; j <= n; ++j)
        maximize(up[i + j - 1], getSum(sa, i - A + 1, j - B + 1, i, j));
    for (int i = 1; i <= mn; ++i) maximize(up[i], up[i - 1]);
    for (int i = K + 1; i + K <= m; ++i) for (int j = K + 1; j + K <= n; ++j)
        maximize(down[i + j - 1 - K], diamond[i][j]);
    for (int i = mn - 1; i >= 1; --i) maximize(down[i], down[i + 1]);
    for (int i = A + B - 1; i <= mn; ++i) maximize(ans, up[i] + down[i + 1]);
}

long long temp[N][N];

void rotateBoard() {
    for (int i = 1; i <= m; ++i) for (int j = 1; j <= n; ++j)
        temp[j][m - i + 1] = a[i][j];
    swap(m, n); swap(A, B);
    for (int i = 1; i <= m; ++i) for (int j = 1; j <= n; ++j) a[i][j] = temp[i][j];
}

void initialize() {
    for (int i = 0; i <= mn + 1; ++i) for (int j = 0; j <= mn + 1; ++j) b[i][j] = 0;
    for (int i = 1; i <= m; ++i) for (int j = 1; j <= n; ++j) b[i + j - 1][i - j + n] = a[i][j];
    buildS(a, sa, m, n);
    buildS(b, sb, mn, mn);
    for (int i = 1; i <= m; ++i) for (int j = 1; j <= n; ++j) diamond[i][j] = -INF;
    for (int i = K + 1; i + K <= m; ++i) for (int j = K + 1; j + K <= n; ++j) {
        int x = i + j - 1, y = i - j + n;
        diamond[i][j] = getSum(sb, x - K, y - K, x + K, y + K);
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin >> m >> n >> A >> B >> K;
    mn = m + n - 1;
    for (int i = 1; i <= m; ++i) for (int j = 1; j <= n; ++j) cin >> a[i][j];
    ans = -INF;
    for (int it = 1; it <= 4; ++it) {
        rotateBoard();
        initialize();
        solveLine();
        solveDiag();
    }
    if (ans <= -(long long)1e15) {
        cout << "no solution\n";
        return 0;
    }
    cout << ans << endl;
    return 0;
}