1451번: 직사각형으로 나누기

https://www.acmicpc.net/problem/1451


$O(n^2+m^2)$

경계는 T자, ||자와 이것을 돌린 모양만 가능하다.
모든 경우를 고려해 답을 구하자.
직사각형 합은 prefix sum을 이용한다.

#include<cstdio>
#include<algorithm>
using namespace std;
int n, m;
long long s[101][101], r;
long long f(int x1, int y1, int x2, int y2) { return s[x2][y2] - s[x1][y2] - s[x2][y1] + s[x1][y1]; }
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) scanf("%1lld", &s[i][j]), s[i][j] += s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1];
    for (int i = 1; i < n; i++)
        for (int j = 1; j < m; j++)
            r = max({ r,s[i][m] * f(i,0,n,j)*f(i,j,n,m),
                s[n][j] * f(0,j,i,m)*f(i,j,n,m),
                s[i][j] * f(0,j,n,m)*f(i,0,n,j),
                s[i][j] * f(0,j,i,m)*f(i,0,n,m) });
    for (int i = 1; i < n; i++)
        for (int j = i + 1; j <= n; j++) r = max(r, s[i][m] * f(i, 0, j, m)*f(j, 0, n, m));
    for (int i = 1; i < m; i++)
        for (int j = i + 1; j <= m; j++) r = max(r, s[n][i] * f(0, i, n, j)*f(0, j, n, m));
    printf("%lld", r);
    return 0;
}