Hình chữ nhật 0 1

Xem dạng PDF
Gửi bài giải
Điểm: 0,12 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 512M
Input: stdin
Output: stdout
Nguồn bài:
Ðược add lên bởi Võ Khánh Trung
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Cho một bảng kích thước ~M \times N~, được chia thành lưới ô vuông đơn vị ~M~ dòng ~N~ cột ~(1 \leq M~, ~N \leq 1000)~

Trên các ô của bảng ghi số ~0~ hoặc 1. Các dòng của bảng được đánh số ~1~, ~2~, ..., ~M~ theo thứ tự từ trên xuống dưới và các cột của bảng được đánh số ~1~, ~2~, ..., ~N~ theo thứ tự từ trái qua phải.

Yêu cầu:

Hãy tìm một hình chữ nhật gồm các ô của bảng thoả mãn các điều kiện sau:

  • Hình chữ nhật đó chỉ gồm các số ~1~
  • Cạnh hình chữ nhật song song với cạnh bảng
  • Diện tích hình chữ nhật là lớn nhất có thể

Input

Dòng ~1~: Ghi hai số ~M~, ~N~

Dòng thứ ~i~ trong ~M~ dòng tiếp theo: Ghi ~N~ số mà số thứ ~j~ là số ghi trên ô ~(i~, ~j)~ của bảng

Output

Gồm ~1~ dòng duy nhất ghi diện tích của hình chữ nhật tìm được

Sample Input

11 13
0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 1 1 1 0 0 0 0 0 0
0 0 1 1 1 1 1 1 1 0 0 0 0
0 0 1 1 1 1 1 1 1 0 0 0 0
0 1 1 1 1 1 1 1 1 1 0 0 0
1 1 1 1 1 1 1 1 1 1 1 0 0
0 1 1 1 1 1 1 1 1 1 0 0 0
0 0 1 1 1 1 1 1 1 0 0 0 0
0 0 1 1 1 1 1 1 1 0 0 0 0
0 0 0 0 1 1 1 0 0 0 0 1 1
0 0 0 0 0 1 0 0 0 0 0 1 1

Sample Output

49

Bình luận

Hãy đọc nội quy trước khi bình luận.


  • -1
    vominhmanh10  đã bình luận lúc 20, Tháng 11, 2025, 8:42

    stack đơn điệu để giải trọn vẹn, đã debug:
    dấu >= để dãy tăng nghiêm ngặc
    mặc định l[i] = -1 khi không có bên trái và r[j] = n khi không có bên phải

    #include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define IO ios::sync_with_stdio(0)
int n, m;
vector<vector<int>> a;
int main() {
    IO;
    cin >> m >> n; a.resize(m, vector<int>(n));
    for (auto &x : a)
        for (int &y : x) cin >> y;

    int res = 0;
    vector<int> h(n, 0);
    for (auto b : a) {
        for (int i = 0; i < n; i++) {
            if (b[i] == 1) h[i]++;
            else h[i] = 0;
        }
        vector<int> l(n, -1), r(n, n);
        stack<int> L, R;
        for (int i = 0; i < n; i++) {
            int j = n - i - 1;
            while (!L.empty() && h[L.top()] >= h[i]) L.pop();
            while (!R.empty() && h[R.top()] >= h[j]) R.pop();
            if (!L.empty()) l[i] = L.top();
            if (!R.empty()) r[j] = R.top();
            L.push(i); R.push(j);
        }
        for (int i = 0; i < n; i++) res = max((r[i] - l[i] - 1) * h[i], res);
    }
    cout << res;
}

  • 1
    tunbeo2021  đã bình luận lúc 1, Tháng 10, 2025, 9:43

    Timelimit hơi yếu thì phải, mình làm O(n * m^2) vẫn pass


  • -18
    nguyenthingoc22031969  đã bình luận lúc 5, Tháng 3, 2024, 1:09

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • 22
    hieplpvip  đã bình luận lúc 21, Tháng 9, 2021, 10:09

    Mình đã thêm test do bạn phucsongdonggia đóng góp và vài submission đã mất AC.


  • 62
    phucsongdonggia  đã bình luận lúc 21, Tháng 9, 2021, 9:37

    Em thấy bài em vẫn còn 1 lỗ hổng mà vẫn AC. Đáp án là 20 nhưng theo cách chạy của bài em sẽ ra 16. Mong ad sẽ bổ sung thêm test này <3

    6 8

    0 0 1 0 0 0 0 0

    1 0 1 0 1 1 1 1

    1 0 1 0 1 1 1 1

    1 0 1 0 1 1 1 1

    1 0 1 0 1 1 1 1

    1 1 1 1 1 1 1 1


    • -219
      hungco1ny  đã bình luận lúc 18, Tháng 10, 2021, 14:53 ← sửa 2

      Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


      • 45
        leduykhongngu  đã bình luận lúc 18, Tháng 10, 2021, 14:54

        bạn bị cấm bình luận do ngôn ngữ thô tục nhé