Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

LSEA - Vùng biển của Lulu

Lulu là tên của một chú hải cẩu. Chú ta cai quản một vùng biển rộng. Vùng biển ấy bao gồm đảo (phần cạn), ao, hồ, các con sông (phần nước trên đất liền) và biển xung quanh các đảo (phần nước dưới biển). Để tiện việc quản lí, Lulu đã vẽ bản đồ cho vùng biển của mình. Bản đồ có thể xem như một ảnh hình chữ nhật có kích thước các cạnh là M, N và bao gồm M*N bit trắng đen. Mỗi bit sẽ tương ứng với một mảnh đất đơn vị trên thực tế. Bit đen sẽ tượng trưng cho phần cạn và bit trắng sẽ tượng trưng cho phần nước.

Vùng biển của Lulu vừa mới được UNESCO công nhận là Di sản tự nhiên của Thế giới. Nên các nhà đầu tư ào ạt đổ tới đây để xây các Resort, khu nghỉ mát, nghỉ dưỡng, v.v... Họ sẽ mua những mảnh đất có hình chữ nhật. Và vì được sử dụng đế xây các khu du lịch biển, nên mảnh đất đó phải có cả phần nước và phần cạn. Họ gọi những mảnh đất như thế là những mảnh đất đẹp.

Sau khi biết điều này, Lulu sẽ bán các mảnh đất của mình như sau:

  • Các mảnh đất được bán phải nằm khít trên bản đồ.
  • Không chấp nhận việc chia nhỏ một mảnh đất đơn vị để bán.
  • Giá bán của một mảnh đất đơn vị là số mảnh đất đẹp mà nó nằm trên.
  • Giá bán của một mảnh đất bất kì là tổng giá bán của các mảnh đất đơn vị của nó.

Alex là một đại gia nổi tiếng trên thế giới. Anh ấy đã quyết định mua hết cả vùng biển M*N của Lulu. Việc khảo sát giá của 1 mảnh đất đơn vị hay 2 mảnh đất đơn vị hay 3 mảnh đất đơn vị là chuyện nhỏ đối với Lulu. Nhưng giờ đây lại phải cùng lúc khảo sát đến tất cả là M*N mảnh đất đơn vị, đó là một điều không thể nào kết thúc trong nháy mắt được.

Bây giờ bạn là người được thuê để tính toán hộ số tiền Alex phải trả.

Giới hạn

  • 1 ≤ M, N ≤ 2000.
  • 30% số test có M, N ≤ 20.
  • 50% số test có M, N ≤ 100.

Input

  • Dòng đầu tiên 2 số M, N cho biết kích thước của vùng biển Lulu sở hữu.
  • M dòng sau, mỗi dòng một dãy gồm N bit (0 hoặc 1) cho biết bản đồ của vùng biển (0 là trắng, 1 là đen).

Output

  • Một số duy nhất là kết quả của bài toán.

Example

Input:
2 2
01
01
Output: 8

(Trong lúc thi, sẽ chấm trước 4 test (bao gồm test ví dụ)).


Được gửi lên bởi:Alex & Friends
Ngày:2012-12-10
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: GOSU PERL6 PYPY RUST SED
Nguồn bài:Tranhu Thái Huy - C11 Contest Round 20

hide comments
2012-12-18 04:08:05 ๖Thằng ๖Hề ๖Khóc
TLE hay sao mak dk có 70 nhỉ :?

Re: bạn bị TLE

Last edit: 2012-12-18 16:38:58
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.