TLEoj Contest #09 - Nhà cây - TLEOJ: TLE Online Judge

TLEoj Contest #09 - Nhà cây

Điểm: 1750 (thành phần)

Thời gian: 1.0s

Bộ nhớ: 512M

Input: bàn phím

Output: màn hình

Tác giả:

Lib

Dạng bài

Tọa lạc tại vị trí vô cùng đắc địa, phòng 702 D4 trường THPT Chuyên Sư Phạm tự hào là hàng net lâu đời nhất nhì và chắc chắn là cao nhất đường Xuân Thủy - Nơi mà máy nào máy nấy đều có case máy đèn 7 màu, người người nhà nhà đều mang bàn phím custom đi, máy nào cũng có Steam, không thì Genshin hoặc Y8 browser. Ngày hôm nay, các thành viên K56 Tin gồm SpiceDangSpice, Lib, NotNaCl, Kubogi, Normankr07 đang tranh thủ ngồi chơi Minecraft trong lúc chờ thầy Hoàng setup server CSPOI (họ không biết rằng thầy đang setup 2 bài matching và 4 bài mincost flow).

Do đã quá chán nản với việc làm theo Geneva Suggestions và làm đủ các thứ trò con bò, họ đã quyết định: Thay vì tiếp tục mở rộng danh sách "tội ác chống lại loài người" của mình, hôm nay, họ sẽ làm thứ gì đó "Zen" hơn: Xây nhà. Tuy nhiên, do bản tính siêu sv đã ắn sâu vào trong máu, các thành viên lớp 11D6 không thể nào chịu được việc phải đặt các block xuống để xây nhà. Trong hoàn cảnh đó, Lib đã nghĩ ra 1 ý tưởng siêu thiên tài: Phá rừng để làm nhà (vẫn không phải Crimes Against Humanity nhé).

Sau khoảng $10$ phút đi tìm $1$ mảnh rừng chưa bị cháy thành tro, các thành viên lớp 11D6 đã tìm được $1$ mảnh đất có kích thước $M \times N$ block. Các hàng được đánh số từ $1$ đến $M$ , các cột được đánh số từ $1$ đến $N$ . Trong mảnh rừng này, ở ô $[i][j]$ sẽ có giá trị là $0$ nếu ở đó không có cây nào, ngược lại ô $[i][j]$ sẽ có giá trị là $1$ . $1$ ngôi nhà cần phải có dạng $1$ hình vuông kích thước $A \times A$ , với tất cả các ô ở trên cạnh đều phải có sẵn cây (để làm tường), và tất cả các ô không nằm trên cạnh của ngôi nhà đều phải không có cây nào. Dĩ nhiên, để tìm được $1$ khu đất đủ to mà không chứa cây nào trong tự nhiên là rất khó, nên vẫn có thể chặt $1$ số cây đi được. Tuy nhiên, do chỉ còn $3$ ngày nữa là thi tuyển, và không ai muốn bị đánh giá là quá nghiện ngập, mải chơi không lo học bởi một Mrs REDACTED nào đó, tập thể sv lớp 11D6 chỉ được phép chặt tối đa không quá $K$ cây.

Yêu cầu: Tính diện tích của ngôi nhà lớn nhất mà các thành viên lớp 11D6 có thể "xây" được thỏa mãn các yêu cầu của đề bài.

Input, Output and Subtasks

Input

Dòng 1 là $3$ số nguyên dương $M, N, K$ .
$M$ dòng tiếp theo, mỗi dòng là $N$ số chỉ trạng thái của ô $[i][j]$ .
Dữ liệu đề bài đảm bảo $M, N\le 6000$ trong mọi testcase.

Output

Gồm 1 số nguyên là diện tích của ngôi nhà lớn nhất tìm được.

Subtasks

Có $20\%$ số testcase có $K=0$
Có $30\%$ số testcase có $K=1$
$50\%$ testcase còn lại, K không có điều kiện gì thêm
1) $40\%$ số điểm: $M,N\le 300$
2) $30\%$ số điểm: $M\times N\le 10^6$
3) $30\%$ số điểm: $M\times N\le 5\times 10^6$ .

Example 1

Input

9 12 0
0 1 0 1 0 1 1 0 1 1 0 0 
1 1 1 1 1 0 0 0 0 1 1 0  
1 0 1 1 1 1 1 1 1 1 1 1 
1 1 0 1 0 1 0 0 0 1 0 1 
0 1 1 1 1 1 0 0 0 1 0 1 
1 0 1 0 0 1 0 0 0 1 1 0 
0 1 1 0 0 1 1 1 1 1 0 1 
1 1 0 1 1 1 0 0 1 1 1 0 
1 1 1 1 0 1 0 0 0 1 1 0

Output

Example 2

Input

13 12 1
0 0 0 0 0 0 1 0 0 1 0 0 
0 0 0 1 0 1 1 1 0 0 1 0 
0 1 0 1 1 1 0 1 0 0 1 1 
1 0 1 1 1 1 1 0 1 0 1 1 
1 1 1 0 0 0 1 1 1 0 1 0 
0 1 1 0 0 0 1 0 1 0 0 1 
0 0 1 0 0 1 1 0 0 0 1 0 
1 1 1 1 1 1 1 1 0 1 0 0 
0 1 1 0 1 0 0 1 0 1 0 1 
0 0 0 0 0 0 0 0 0 0 0 0 
0 1 0 1 0 0 1 1 0 1 1 1 
0 0 0 0 1 1 0 0 0 0 0 0 
0 0 1 0 0 1 0 0 0 1 0 1

Output

Example 3

Input

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

Output

Bình luận

Không có bình luận nào.