Bảng con đậm đặc
Cho bảng $M\times N$. Ô ở hàng thứ $i$, cột $j$ có giá trị $a_{i,j}$. Một bảng con được gọi là đậm đặc nếu chứa toàn bộ ô có giá trị dương.
Hãy đếm số lượng bảng con đậm đặc.
Dữ liệu
- Dòng đầu tiên chứa số nguyên $N, M \ (1\le N,M \le 10^3)$;
- $N$ dòng tiếp theo, mỗi dòng chứa $M$ số nguyên $a_{i,j} \ (|a_{i,j}| \le 10^9)$.
Kết quả
- Kết quả bài toán.
Chấm điểm
30;$M, N \le 10$. 30;$M, N \le 80$. 40;Không có giới hạn gì thêm.
Ví dụ
Ví dụ 1
input
3 5
0 1 1 0 0
1 1 1 1 0
0 0 1 1 1
output
26
Comments