Codeforces Round #221 (Div. 1) B. Maximum Submatrix 2

問題

codeforces.com

解法

maxi[row][l] = (row 行目の l 番目の要素から始めると, 1 が最大どこまで連続しているか) というのを, 各行 row について, しゃくとりっぽく O(m) で求めます。

そしたら, l 列目からスタートする長方形について, 面積が最大にすることを考えます。maxi[row][l] がわかっているので, 各行で どこまで長方形が valid かは O(1) でわかりますが, この v[row] = maxi[row][l] を大きい順にソートして,

        int len = m;
        for (int i = 0; i < n; i++) {
            len = min(len, v[i]-l);
            ans = max(ans, (i+1)*len);
        }

という感じで len を短いものに合わせながら, 縦の長さを伸ばしていき, その都度面積をチェックしていけば最大の面積が得られます。
普通に sort() を使ったので自分のアルゴリズムは O(nmlog(n)) ですが, 想定解ではバケツソートを使っているので O(nm) でした。実際 C++ でも O(nmlog(n)) は 1.5 秒以上かかってるので危ないです(多少は高速化出来る余地がありますが)。

const int MAX = 5055;
int mat[MAX][MAX];
int maxi[MAX][MAX];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < m; j++) mat[i][j] = s[j]-'0';
    }
    for (int i = 0; i < n; i++) {
        int l = 0, r = 0;
        while (l < m) {
            if (mat[i][l] == 0) {
                l++;
            } else {
                r = l;
                while (r < m && mat[i][r] == 1) {
                    r++;
                }
                for (int j = l; j < r; j++) maxi[i][j] = r;
                l = r+1;
            }
        }
    }
    int ans = 0;
    for (int l = 0; l < m; l++) {
        vector<int> v(n);
        for (int i = 0; i < n; i++) v[i] = maxi[i][l];
        sort(v.rbegin(), v.rend());
        int len = m;
        for (int i = 0; i < n; i++) {
            len = min(len, v[i]-l);
            ans = max(ans, (i+1)*len);
        }
    }
    cout << ans << endl;
    return 0;
}