Codeforces Round #221 (Div. 1) B. Maximum Submatrix 2
解法
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; }