#1271. BOB

Bộ nhớ: 256 MiB Thời gian: 500 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Chùm CUỐI

Đề bài

Bob mua một khu đất có dạng hình chữ nhật có chiều rộng là N mét và chiều cao là M mét, và mảnh đất được chia thành M×N ô vuông nhỏ, mỗi ô vuông có một độ cao khác nhau.

Bob muốn xây một ngôi nhà trên mảnh đất này. Anh muốn chọn một khu đất hình chữ nhật, có các cạnh song song với cạnh của mảnh đất, tuy nhiên, độ cao của tất cả ô đất trong vùng được chọn phải bằng nhau.

Hãy đếm số cách Bob có thể chọn khu vực để xây nhà.

Dữ liệu vào:

  • Dòng đầu tiên là hai số N M\ (1≤N,M≤1000) ;
  • N dòng sau, mỗi dòng gồm M số, số thứ j của hàng i là giá trị a_{ij} thể hiện chiều cao của ô đất có tọa độ (i, j)\ (a_{ij}≤10^9) .

Dữ liệu ra:

  • Số nguyên duy nhất là kết quả của bài toán.

Ví dụ:

Dữ liệu vào:
5 3
2 2 2
2 2 1
1 1 1
2 1 2
1 2 1
Dữ liệu ra:
27
Dữ liệu vào:
4 3
1 1 1
1 1 1
2 2 2
2 2 2
Dữ liệu ra:
36

Giới hạn:

  • 20\% N,M≤50 ;
  • 40\% N,M≤500 .