[BOJ 2829] 아름다운 행렬

우하단 / 좌하단 대각선 누적합을 각각 진행해주고, (x, y)에서 변의 길이가 k인 형태에서의 아름다운 정도를 구해서 답을 갱신해주면 된다. $O(N^3)$으로 해결 가능하다.

int N, A[MAXN][MAXN], B[MAXN][MAXN];

int main(void) {
    fastio;
    cin >> N;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> A[i][j];
            B[i][j] += B[i - 1][j + 1] + A[i][j];   // B 좌하단 대각선 누적합 
            A[i][j] += A[i - 1][j - 1];             // A 우하단 대각선 누적합 
        }
    }

    int ans = -INF;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            for (int k = 0; k <= N - max(i, j); k++) {
                int x1 = j, x2 = j + k;
                int y1 = i, y2 = i + k;
                int beautiful = (A[y2][x2] - A[y1 - 1][x1 - 1]) 
                                - (B[y2][x1] - B[y1 - 1][x2 + 1]);
                ans = max(ans, beautiful);
            }
        }
    }
    cout << ans;
    return 0;
}