BOJ 2829 - 아름다운 행렬

BOJ - 아름다운 행렬

대각선으로 구간합 배열을 두개 만들어주고 $O(N^3)$ 에 모든 경우를 순회하면서 정답을 구해줍니다.

void solve() {
   int n;
   cin >> n;
   vvi a(n, vi(n));
   fv2(a);
   vvi dpa(n, vi(n)), dpb(n, vi(n));

   for (int y = 0; y < n; y++) {
      for (int x = 0; x < n; x++) {
         dpa[y][x] += a[y][x];
         dpb[y][x] += a[y][x];
         if (y && x) dpa[y][x] += dpa[y - 1][x - 1];
         if (y && x < n - 1) dpb[y][x] += dpb[y - 1][x + 1];
      }
   }
   int ans = -1e9;
   for (int y = 0; y < n; y++) {
      for (int x = 0; x < n; x++) {
         for (int k = 0; k <= min(x, y); k++) {
            int A = dpa[y][x] - (y - k == 0 || x - k == 0 ? 0 : dpa[y - k - 1][x - k - 1]);
            int B = dpb[y][x - k] - (y - k == 0 || x == n - 1 ? 0 : dpb[y - k - 1][x + 1]);
            ans = max(ans, A - B);
         }
      }
   }
   cout << ans;
}