Hướng dẫn giải của Hái hoa

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Ý tưởng là xoay ma trận ~45~ độ để biến bài toán thành bài toán truy vấn tổng hình chữ nhật trên ma trận quen thuộc. Ví dụ:
```
1 2 3            0 0 1 0 0
4 5 6   -->      0 4 0 2 0
7 8 9            7 0 5 0 3
                 0 8 0 6 0
                 0 0 9 0 0
```

Code mẫu:

#include <bits/stdc++.h>

#define int long long
#define endl "\n"

using namespace std;

const int MOD = 1e9 + 7;
const int MAXN = 2e5 + 7;

int n, k, a[1007][1007], b[2007][2007], f[2007][2007];

void program(){
    cin >> n >> k;
    // Y tuong: xoay phai hinh vuong 1 goc 45 do: a[][] la mang ban dau => b[][] la mang sau khi xoay
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            cin >> a[i][j];
            int x = i + j - 1;
            int y = j + n - i;
            b[x][y] = a[i][j];
        }
    }
    int N = n + n - 1;
    for(int x = 1; x <= N; x++){
        for(int y = 1; y <= N; y++){
            // f[][] la mcd cua hinh vuong sau khi xoay
            f[x][y] = f[x][y - 1] + f[x - 1][y] - f[x - 1][y - 1] + b[x][y];
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            int x = i + j - 1;
            int y = j + n - i;
            int hangDau = max(1ll,x - k);
            int hangCuoi = min(N, x + k);
            int cotDau = max(1ll, y - k);
            int cotCuoi = min(N, y + k);
            cout << f[hangCuoi][cotCuoi] + f[hangDau - 1][cotDau - 1] - f[hangCuoi][cotDau - 1] - f[hangDau - 1][cotCuoi] << " ";
        }
        cout << endl;
    }

}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    program();
}