H другого чела

#include <bits/stdc++.h>

using namespace std;

const int N = 1600;

int n, m, k, dpp[3][N][N], pref[N][N], dps[3][N][N], ar[N][N], ans;

int main()
{
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            cin >> ar[i][j];
            pref[i][j] = pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1] + ar[i][j];
            if (i >= k && j >= k)
            {
                dpp[1][i][j] = max( pref[i][j] - pref[i][j - k] - pref[i - k][j] + pref[i - k][j - k], max( dpp[1][i - 1][j], dpp[1][i][j - 1] ) );
                dpp[2][i][j] = max( max(dpp[2][i][j - 1], dpp[2][i - 1][j]), pref[i][j] - pref[i][j - k] - pref[i - k][j] + pref[i - k][j - k] + max( dpp[1][i - k][j], dpp[1][i][j - k] ) );
            }
        }
    }
    for (int i = n - k + 1; i >= 1; i--)
    {
        for (int j = m - k + 1; j >= 1; j--)
        {
            dps[1][i][j] = max( pref[i + k - 1][j + k - 1] - pref[i - 1][j + k - 1] - pref[i + k - 1][j - 1] + pref[i - 1][j - 1], max( dps[1][i + 1][j], dps[1][i][j + 1] ) );

            dps[2][i][j] = max( max(dps[2][i + 1][j], dps[2][i][j + 1]), pref[i + k - 1][j + k - 1] - pref[i - 1][j + k - 1] - pref[i + k - 1][j - 1] + pref[i - 1][j - 1] +

                             max( dps[1][i][j + k], dps[1][i + k][j] ) );
        }
    }
    for (int i = 1; i <= n - k + 1; i++)
    {
        for (int j = 1; j <= m - k + 1; j++)
        {
            int sum = pref[i + k - 1][j + k - 1] - pref[i - 1][j + k - 1] - pref[i + k - 1][j - 1] + pref[i - 1][j - 1];
            ans = max( ans, sum + max( max(dpp[2][n][j - 1], dps[2][1][j + k]) , max(dpp[2][i - 1][m], dps[2][i + k][1]) ) );
        }
    }
    cout << ans << endl;
}