TOI11: observatory

#include <bits/stdc++.h>

using namespace std;
const int INF = 2e9;
const int N = 2e3 + 10;
const int M = 2e3 + 10;
int n, m, k;
int ar[N][M];
int qs[N][M];
int rtri[N][M], ltri[N][M];
int lr[N][M], rl[N][M];
int lrdia[N][M], rldia[N][M];

int main(){

    scanf("%d%d%d", &n, &m, &k);

    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            scanf("%d", &ar[i][j]);
        }
    }

    /// rectangle

    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            qs[i][j] = ar[i][j] + qs[i-1][j] + qs[i][j-1] - qs[i-1][j-1];
        }
    }

    /// triangle
        /// left -> right, right -> left
        /// diagonal left -> right, right -> left

    /// left -> right
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            lr[i][j] = lr[i][j-1] + ar[i][j];
        }
    }

    /// right -> left
    for(int i=1;i<=n;i++){
        for(int j=m;j>=1;j--){
            rl[i][j] = rl[i][j+1] + ar[i][j];
        }
    }

    /// diagonal left -> right
    for(int jj=0;jj<=m+1;jj++){
        for(int i=0, j=jj; i<=n+1 and j<=m+1; i++, j++)
            lrdia[i][j] = lrdia[i-1][j-1] + rl[i][j];
    }
    for(int ii=0;ii<=n+1;ii++){
        for(int j=0, i=ii; i<=n+1 and j<=m+1; i++, j++)
            lrdia[i][j] = lrdia[i-1][j-1] + rl[i][j];
    }

    /// diagonal right -> left
    for(int jj=m+1;jj>=0;jj--){
        for(int i=0, j=jj; i<=n+1 and j>=0; i++, j--)
            rldia[i][j] = rldia[i-1][j+1] + lr[i][j];
    }
    for(int ii=0;ii<=n+1;ii++){
        for(int j=m+1, i=ii; i<=n+1 and j>=0; i++, j--)
            rldia[i][j] = rldia[i-1][j+1] + lr[i][j];
    }

    /// query
    int mx = -INF;

    /// left triangle
    for(int i=k;i<=n;i++){
        for(int j=k;j<=m;j++){
            int rectangle = qs[i][m] - qs[i][j-k] - qs[i-k][m] + qs[i-k][j-k];
            int triangle = lrdia[i][j+1] - lrdia[i-k][j-k+1];
            mx = max(mx, rectangle - triangle);
        }
    }

    /// right triangle
    for(int i=k;i<=n;i++){
        for(int j=k;j<=m;j++){
            int rectangle = qs[i][j] - qs[i-k][j];
            int triangle = rldia[i][j-k] - rldia[i-k][j];
            mx = max(mx, rectangle - triangle);
        }
    }

    printf("%d", mx);

    return 0;
}