trang chủ / đề bài / icpc25_mb_a

Món quà

Đề bài

Mô tả

Sắp đến sinh nhật Khánh Đan, Scratch quyết định tự tay làm một món đồ để tặng. Cụ thể, Scratch tự làm một khối gỗ lớn kích thước p×q×r (ghép từ pqr khối đơn vị). Tuy nhiên, do Scratch còn thiếu kinh nghiệm, một số khối đơn vị trong khối lớn bị lỗi (nứt, rỗng bên trong, ...). Scratch không thể tặng một món quà như vậy.

Vì thế, Scratch dự định đục ra từ khối lớn một khối con a×a×b (khối hộp chữ nhật được đục ra phải có hai cạnh kề nhau bằng nhau). Dĩ nhiên, khối con này không được chứa khối đơn vị lỗi nào.

Scratch muốn chọn phương án có giá trị 4ab lớn nhất trong tất cả các phương án có thể. Nhưng chỉ riêng việc kiểm tra xem phần nào của khối bị lỗi đã khiến Scratch kiệt sức. Là bạn tốt của Scratch, bạn hãy giúp cậu ấy nhé!

Dữ liệu vào

Dòng đầu tiên chứa ba số nguyên dương p,q,r (1≤p,q,r≤150), cách nhau bởi dấu cách.

Mỗi dòng trong pq dòng tiếp theo chứa r ký tự, mỗi ký tự là P (khối lỗi) hoặc N (khối bình thường), cho biết khối đơn vị tương ứng bị lỗi hay còn nguyên vẹn. Cụ thể, ký tự thứ z trên dòng thứ (y−1)p+x trong pq dòng này mô tả tình trạng của khối đơn vị ở tọa độ (x,y,z) (1≤x≤p, 1≤y≤q, 1≤z≤r).

Dữ liệu ra

In ra một số nguyên là giá trị 4ab lớn nhất. Khối con có thể nằm theo bất kỳ hướng nào (cặp cạnh bằng nhau có thể song song với bất kỳ hai trục tọa độ nào); nếu mọi khối đơn vị đều lỗi, in ra 0.

Ràng buộc

  • 1≤p,q,r≤150.
  • Mỗi ký tự là P hoặc N.

Ví dụ

Input Output Giải thích
4 3 5
NNNNP
NPNPN
PNPPN
NNNNN
NNNNN
NNNNN
NNNNP
NNPPN
NNPPN
PNNNN
NNNNN
NNPNN
24 Ví dụ của đề gốc. Khối con gồm các ô có x∈{2,3}, y∈{2,3}, z∈{2,3,4} không chứa khối lỗi, cho a=2, b=3, 4ab=24.
2 3 4
NNNN
NNNN
NNNP
NNNN
PNNN
NNNN
24 Ví dụ bổ sung (không có trong đề gốc). Khối con gồm các ô có x∈{1,2}, y∈{1,2}, z∈{1,2,3} không chứa khối lỗi (a=2, b=3). Khối x∈{1,2}, y∈{1,2,3}, z∈{2,3} (cặp cạnh bằng nhau theo trục x và z) cũng cho 4ab=24.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0